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