View Javadoc
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 }