1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.codec.language.bm;
19
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collections;
23 import java.util.EnumMap;
24 import java.util.HashSet;
25 import java.util.LinkedHashSet;
26 import java.util.List;
27 import java.util.Locale;
28 import java.util.Map;
29 import java.util.Objects;
30 import java.util.Set;
31 import java.util.TreeMap;
32 import java.util.stream.Collectors;
33
34 import org.apache.commons.codec.language.bm.Languages.LanguageSet;
35 import org.apache.commons.codec.language.bm.Rule.Phoneme;
36
37 /**
38 * Converts words into potential phonetic representations.
39 * <p>
40 * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
41 * into account the likely source language. Next, this phonetic representation is converted into a
42 * pan-European 'average' representation, allowing comparison between different versions of essentially
43 * the same word from different languages.
44 * </p>
45 * <p>
46 * This class is intentionally immutable and thread-safe.
47 * If you wish to alter the settings for a PhoneticEngine, you
48 * must make a new one with the updated settings.
49 * </p>
50 * <p>
51 * Ported from phoneticengine.php
52 * </p>
53 *
54 * @since 1.6
55 */
56 public class PhoneticEngine {
57
58 /**
59 * Utility for manipulating a set of phonemes as they are being built up. Not intended for use outside
60 * this package, and probably not outside the {@link PhoneticEngine} class.
61 *
62 * @since 1.6
63 */
64 static final class PhonemeBuilder {
65
66 /**
67 * An empty builder where all phonemes must come from some set of languages. This will contain a single
68 * phoneme of zero characters. This can then be appended to. This should be the only way to create a new
69 * phoneme from scratch.
70 *
71 * @param languages the set of languages
72 * @return a new, empty phoneme builder
73 */
74 public static PhonemeBuilder empty(final Languages.LanguageSet languages) {
75 return new PhonemeBuilder(new Rule.Phoneme("", languages));
76 }
77
78 private final Set<Rule.Phoneme> phonemes;
79
80 private PhonemeBuilder(final Rule.Phoneme phoneme) {
81 this.phonemes = new LinkedHashSet<>();
82 this.phonemes.add(phoneme);
83 }
84
85 private PhonemeBuilder(final Set<Rule.Phoneme> phonemes) {
86 this.phonemes = phonemes;
87 }
88
89 /**
90 * Creates a new phoneme builder containing all phonemes in this one extended by {@code str}.
91 *
92 * @param str the characters to append to the phonemes
93 */
94 public void append(final CharSequence str) {
95 phonemes.forEach(ph -> ph.append(str));
96 }
97
98 /**
99 * Applies the given phoneme expression to all phonemes in this phoneme builder.
100 * <p>
101 * This will lengthen phonemes that have compatible language sets to the expression, and drop those that are
102 * incompatible.
103 * </p>
104 *
105 * @param phonemeExpr the expression to apply
106 * @param maxPhonemes the maximum number of phonemes to build up
107 */
108 public void apply(final Rule.PhonemeExpr phonemeExpr, final int maxPhonemes) {
109 final Set<Rule.Phoneme> newPhonemes = new LinkedHashSet<>(Math.min(phonemes.size() * phonemeExpr.size(), maxPhonemes));
110 EXPR: for (final Rule.Phoneme left : phonemes) {
111 for (final Rule.Phoneme right : phonemeExpr.getPhonemes()) {
112 final LanguageSet languages = left.getLanguages().restrictTo(right.getLanguages());
113 if (!languages.isEmpty()) {
114 final Rule.Phoneme join = new Phoneme(left, right, languages);
115 if (newPhonemes.size() < maxPhonemes) {
116 newPhonemes.add(join);
117 if (newPhonemes.size() >= maxPhonemes) {
118 break EXPR;
119 }
120 }
121 }
122 }
123 }
124 phonemes.clear();
125 phonemes.addAll(newPhonemes);
126 }
127
128 /**
129 * Gets underlying phoneme set. Please don't mutate.
130 *
131 * @return the phoneme set
132 */
133 public Set<Rule.Phoneme> getPhonemes() {
134 return phonemes;
135 }
136
137 /**
138 * Stringifies the phoneme set. This produces a single string of the strings of each phoneme,
139 * joined with a pipe. This is explicitly provided in place of toString as it is a potentially
140 * expensive operation, which should be avoided when debugging.
141 *
142 * @return the stringified phoneme set
143 */
144 public String makeString() {
145 return phonemes.stream().map(Rule.Phoneme::getPhonemeText).collect(Collectors.joining("|"));
146 }
147 }
148
149 /**
150 * A function closure capturing the application of a list of rules to an input sequence at a particular offset.
151 * After invocation, the values {@code i} and {@code found} are updated. {@code i} points to the
152 * index of the next char in {@code input} that must be processed next (the input up to that index having been
153 * processed already), and {@code found} indicates if a matching rule was found or not. In the case where a
154 * matching rule was found, {@code phonemeBuilder} is replaced with a new builder containing the phonemes
155 * updated by the matching rule.
156 * <p>
157 * Although this class is not thread-safe (it has mutable unprotected fields), it is not shared between threads
158 * as it is constructed as needed by the calling methods.
159 * </p>
160 *
161 * @since 1.6
162 */
163 private static final class RulesApplication {
164
165 private final Map<String, List<Rule>> finalRules;
166 private final CharSequence input;
167 private final PhonemeBuilder phonemeBuilder;
168 private int i;
169 private final int maxPhonemes;
170 private boolean found;
171
172 public RulesApplication(final Map<String, List<Rule>> finalRules, final CharSequence input, final PhonemeBuilder phonemeBuilder, final int i,
173 final int maxPhonemes) {
174 Objects.requireNonNull(finalRules, "finalRules");
175 this.finalRules = finalRules;
176 this.phonemeBuilder = phonemeBuilder;
177 this.input = input;
178 this.i = i;
179 this.maxPhonemes = maxPhonemes;
180 }
181
182 public int getI() {
183 return i;
184 }
185
186 public PhonemeBuilder getPhonemeBuilder() {
187 return phonemeBuilder;
188 }
189
190 /**
191 * Invokes the rules. Loops over the rules list, stopping at the first one that has a matching context
192 * and pattern. Then applies this rule to the phoneme builder to produce updated phonemes. If there was no
193 * match, {@code i} is advanced one and the character is silently dropped from the phonetic spelling.
194 *
195 * @return {@code this}
196 */
197 public RulesApplication invoke() {
198 found = false;
199 int patternLength = 1;
200 final List<Rule> rules = finalRules.get(input.subSequence(i, i + patternLength));
201 if (rules != null) {
202 for (final Rule rule : rules) {
203 final String pattern = rule.getPattern();
204 patternLength = pattern.length();
205 if (rule.patternAndContextMatches(input, i)) {
206 phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
207 found = true;
208 break;
209 }
210 }
211 }
212
213 if (!found) {
214 patternLength = 1;
215 }
216
217 i += patternLength;
218 return this;
219 }
220
221 public boolean isFound() {
222 return found;
223 }
224 }
225
226 private static final int DEFAULT_MAX_PHONEMES = 20;
227
228 private static final Map<NameType, Set<String>> NAME_PREFIXES = new EnumMap<>(NameType.class);
229
230 static {
231 NAME_PREFIXES.put(NameType.ASHKENAZI,
232 Collections.unmodifiableSet(
233 new HashSet<>(Arrays.asList("bar", "ben", "da", "de", "van", "von"))));
234 NAME_PREFIXES.put(NameType.SEPHARDIC,
235 Collections.unmodifiableSet(
236 new HashSet<>(Arrays.asList("al", "el", "da", "dal", "de", "del", "dela", "de la",
237 "della", "des", "di", "do", "dos", "du", "van", "von"))));
238 NAME_PREFIXES.put(NameType.GENERIC,
239 Collections.unmodifiableSet(
240 new HashSet<>(Arrays.asList("da", "dal", "de", "del", "dela", "de la", "della",
241 "des", "di", "do", "dos", "du", "van", "von"))));
242 }
243
244 /**
245 * Joins some strings with an internal separator.
246 *
247 * @param strings Strings to join
248 * @param sep String to separate them with
249 * @return a single String consisting of each element of {@code strings} interleaved by {@code sep}
250 */
251 private static String join(final List<String> strings, final String sep) {
252 return strings.stream().collect(Collectors.joining(sep));
253 }
254
255 private final Lang lang;
256
257 private final NameType nameType;
258
259 private final RuleType ruleType;
260
261 private final boolean concat;
262
263 private final int maxPhonemes;
264
265 /**
266 * Generates a new, fully-configured phonetic engine.
267 *
268 * @param nameType
269 * the type of names it will use
270 * @param ruleType
271 * the type of rules it will apply
272 * @param concatenate
273 * if it will concatenate multiple encodings
274 */
275 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concatenate) {
276 this(nameType, ruleType, concatenate, DEFAULT_MAX_PHONEMES);
277 }
278
279 /**
280 * Generates a new, fully-configured phonetic engine.
281 *
282 * @param nameType
283 * the type of names it will use
284 * @param ruleType
285 * the type of rules it will apply
286 * @param concatenate
287 * if it will concatenate multiple encodings
288 * @param maxPhonemes
289 * the maximum number of phonemes that will be handled
290 * @since 1.7
291 */
292 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concatenate, final int maxPhonemes) {
293 if (ruleType == RuleType.RULES) {
294 throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
295 }
296 this.nameType = nameType;
297 this.ruleType = ruleType;
298 this.concat = concatenate;
299 this.lang = Lang.instance(nameType);
300 this.maxPhonemes = maxPhonemes;
301 }
302
303 /**
304 * Applies the final rules to convert from a language-specific phonetic representation to a
305 * language-independent representation.
306 *
307 * @param phonemeBuilder the current phonemes
308 * @param finalRules the final rules to apply
309 * @return the resulting phonemes
310 */
311 private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder,
312 final Map<String, List<Rule>> finalRules) {
313 Objects.requireNonNull(finalRules, "finalRules");
314 if (finalRules.isEmpty()) {
315 return phonemeBuilder;
316 }
317
318 final Map<Rule.Phoneme, Rule.Phoneme> phonemes = new TreeMap<>(Rule.Phoneme.COMPARATOR);
319
320 phonemeBuilder.getPhonemes().forEach(phoneme -> {
321 PhonemeBuilder subBuilder = PhonemeBuilder.empty(phoneme.getLanguages());
322 final String phonemeText = phoneme.getPhonemeText().toString();
323
324 for (int i = 0; i < phonemeText.length();) {
325 final RulesApplication rulesApplication = new RulesApplication(finalRules, phonemeText, subBuilder, i, maxPhonemes).invoke();
326 final boolean found = rulesApplication.isFound();
327 subBuilder = rulesApplication.getPhonemeBuilder();
328
329 if (!found) {
330 // not found, appending as-is
331 subBuilder.append(phonemeText.subSequence(i, i + 1));
332 }
333
334 i = rulesApplication.getI();
335 }
336
337 // the phonemes map orders the phonemes only based on their text, but ignores the language set
338 // when adding new phonemes, check for equal phonemes and merge their language set, otherwise
339 // phonemes with the same text but different language set get lost
340 subBuilder.getPhonemes().forEach(newPhoneme -> {
341 if (phonemes.containsKey(newPhoneme)) {
342 final Rule.Phoneme oldPhoneme = phonemes.remove(newPhoneme);
343 final Rule.Phoneme mergedPhoneme = oldPhoneme.mergeWithLanguage(newPhoneme.getLanguages());
344 phonemes.put(mergedPhoneme, mergedPhoneme);
345 } else {
346 phonemes.put(newPhoneme, newPhoneme);
347 }
348 });
349 });
350
351 return new PhonemeBuilder(phonemes.keySet());
352 }
353
354 /**
355 * Encodes a string to its phonetic representation.
356 *
357 * @param input
358 * the String to encode
359 * @return the encoding of the input
360 */
361 public String encode(final String input) {
362 final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
363 return encode(input, languageSet);
364 }
365
366 /**
367 * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
368 *
369 * @param input
370 * String to phoneticise; a String with dashes or spaces separating each word
371 * @param languageSet
372 * set of possible origin languages
373 * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations of the
374 * input
375 */
376 public String encode(String input, final Languages.LanguageSet languageSet) {
377 final Map<String, List<Rule>> rules = Rule.getInstanceMap(this.nameType, RuleType.RULES, languageSet);
378 // rules common across many (all) languages
379 final Map<String, List<Rule>> finalRules1 = Rule.getInstanceMap(this.nameType, this.ruleType, "common");
380 // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
381 final Map<String, List<Rule>> finalRules2 = Rule.getInstanceMap(this.nameType, this.ruleType, languageSet);
382
383 // tidy the input
384 // lower case is a locale-dependent operation
385 input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
386
387 if (this.nameType == NameType.GENERIC) {
388 if (input.startsWith("d'")) { // check for d'
389 final String remainder = input.substring(2);
390 final String combined = "d" + remainder;
391 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
392 }
393 for (final String l : NAME_PREFIXES.get(this.nameType)) {
394 // handle generic prefixes
395 if (input.startsWith(l + " ")) {
396 // check for any prefix in the words list
397 final String remainder = input.substring(l.length() + 1); // input without the prefix
398 final String combined = l + remainder; // input with prefix without space
399 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
400 }
401 }
402 }
403
404 final List<String> words = Arrays.asList(input.split("\\s+"));
405 final List<String> words2 = new ArrayList<>();
406
407 // special-case handling of word prefixes based upon the name type
408 switch (this.nameType) {
409 case SEPHARDIC:
410 words.forEach(aWord -> {
411 final String[] parts = aWord.split("'", -1);
412 words2.add(parts[parts.length - 1]);
413 });
414 words2.removeAll(NAME_PREFIXES.get(this.nameType));
415 break;
416 case ASHKENAZI:
417 words2.addAll(words);
418 words2.removeAll(NAME_PREFIXES.get(this.nameType));
419 break;
420 case GENERIC:
421 words2.addAll(words);
422 break;
423 default:
424 throw new IllegalStateException("Unreachable case: " + this.nameType);
425 }
426
427 if (this.concat) {
428 // concat mode enabled
429 input = join(words2, " ");
430 } else if (words2.size() == 1) {
431 // not a multi-word name
432 input = words.iterator().next();
433 } else if (!words2.isEmpty()) {
434 // encode each word in a multi-word name separately (normally used for approx matches)
435 final StringBuilder result = new StringBuilder();
436 words2.forEach(word -> result.append("-").append(encode(word)));
437 // return the result without the leading "-"
438 return result.substring(1);
439 }
440
441 PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
442
443 // loop over each char in the input - we will handle the increment manually
444 for (int i = 0; i < input.length();) {
445 final RulesApplication rulesApplication =
446 new RulesApplication(rules, input, phonemeBuilder, i, maxPhonemes).invoke();
447 i = rulesApplication.getI();
448 phonemeBuilder = rulesApplication.getPhonemeBuilder();
449 }
450
451 // Apply the general rules
452 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
453 // Apply the language-specific rules
454 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
455
456 return phonemeBuilder.makeString();
457 }
458
459 /**
460 * Gets the Lang language guessing rules being used.
461 *
462 * @return the Lang in use
463 */
464 public Lang getLang() {
465 return this.lang;
466 }
467
468 /**
469 * Gets the maximum number of phonemes the engine will calculate for a given input.
470 *
471 * @return the maximum number of phonemes
472 * @since 1.7
473 */
474 public int getMaxPhonemes() {
475 return this.maxPhonemes;
476 }
477
478 /**
479 * Gets the NameType being used.
480 *
481 * @return the NameType in use
482 */
483 public NameType getNameType() {
484 return this.nameType;
485 }
486
487 /**
488 * Gets the RuleType being used.
489 *
490 * @return the RuleType in use
491 */
492 public RuleType getRuleType() {
493 return this.ruleType;
494 }
495
496 /**
497 * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
498 *
499 * @return true if multiple phonetic encodings are returned, false if just the first is
500 */
501 public boolean isConcat() {
502 return this.concat;
503 }
504 }