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    *      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<>(maxPhonemes);
110 
111             EXPR: for (final Rule.Phoneme left : this.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 
126             this.phonemes.clear();
127             this.phonemes.addAll(newPhonemes);
128         }
129 
130         /**
131          * Gets underlying phoneme set. Please don't mutate.
132          *
133          * @return  the phoneme set
134          */
135         public Set<Rule.Phoneme> getPhonemes() {
136             return this.phonemes;
137         }
138 
139         /**
140          * Stringifies the phoneme set. This produces a single string of the strings of each phoneme,
141          * joined with a pipe. This is explicitly provided in place of toString as it is a potentially
142          * expensive operation, which should be avoided when debugging.
143          *
144          * @return  the stringified phoneme set
145          */
146         public String makeString() {
147             return phonemes.stream().map(Rule.Phoneme::getPhonemeText).collect(Collectors.joining("|"));
148         }
149     }
150 
151     /**
152      * A function closure capturing the application of a list of rules to an input sequence at a particular offset.
153      * After invocation, the values {@code i} and {@code found} are updated. {@code i} points to the
154      * index of the next char in {@code input} that must be processed next (the input up to that index having been
155      * processed already), and {@code found} indicates if a matching rule was found or not. In the case where a
156      * matching rule was found, {@code phonemeBuilder} is replaced with a new builder containing the phonemes
157      * updated by the matching rule.
158      *
159      * Although this class is not thread-safe (it has mutable unprotected fields), it is not shared between threads
160      * as it is constructed as needed by the calling methods.
161      * @since 1.6
162      */
163     private static final class RulesApplication {
164         private final Map<String, List<Rule>> finalRules;
165         private final CharSequence input;
166 
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,
173                                 final PhonemeBuilder phonemeBuilder, final int i, 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 this.i;
184         }
185 
186         public PhonemeBuilder getPhonemeBuilder() {
187             return this.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             this.found = false;
199             int patternLength = 1;
200             final List<Rule> rules = this.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(this.input, this.i)) {
206                         this.phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
207                         this.found = true;
208                         break;
209                     }
210                 }
211             }
212 
213             if (!this.found) {
214                 patternLength = 1;
215             }
216 
217             this.i += patternLength;
218             return this;
219         }
220 
221         public boolean isFound() {
222             return this.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 concat
273      *            if it will concatenate multiple encodings
274      */
275     public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat) {
276         this(nameType, ruleType, concat, 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 concat
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 concat,
293                           final int maxPhonemes) {
294         if (ruleType == RuleType.RULES) {
295             throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
296         }
297         this.nameType = nameType;
298         this.ruleType = ruleType;
299         this.concat = concat;
300         this.lang = Lang.instance(nameType);
301         this.maxPhonemes = maxPhonemes;
302     }
303 
304     /**
305      * Applies the final rules to convert from a language-specific phonetic representation to a
306      * language-independent representation.
307      *
308      * @param phonemeBuilder the current phonemes
309      * @param finalRules the final rules to apply
310      * @return the resulting phonemes
311      */
312     private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder,
313             final Map<String, List<Rule>> finalRules) {
314         Objects.requireNonNull(finalRules, "finalRules");
315         if (finalRules.isEmpty()) {
316             return phonemeBuilder;
317         }
318 
319         final Map<Rule.Phoneme, Rule.Phoneme> phonemes = new TreeMap<>(Rule.Phoneme.COMPARATOR);
320 
321         phonemeBuilder.getPhonemes().forEach(phoneme -> {
322             PhonemeBuilder subBuilder = PhonemeBuilder.empty(phoneme.getLanguages());
323             final String phonemeText = phoneme.getPhonemeText().toString();
324 
325             for (int i = 0; i < phonemeText.length();) {
326                 final RulesApplication rulesApplication = new RulesApplication(finalRules, phonemeText, subBuilder, i, maxPhonemes).invoke();
327                 final boolean found = rulesApplication.isFound();
328                 subBuilder = rulesApplication.getPhonemeBuilder();
329 
330                 if (!found) {
331                     // not found, appending as-is
332                     subBuilder.append(phonemeText.subSequence(i, i + 1));
333                 }
334 
335                 i = rulesApplication.getI();
336             }
337 
338             // the phonemes map orders the phonemes only based on their text, but ignores the language set
339             // when adding new phonemes, check for equal phonemes and merge their language set, otherwise
340             // phonemes with the same text but different language set get lost
341             subBuilder.getPhonemes().forEach(newPhoneme -> {
342                 if (phonemes.containsKey(newPhoneme)) {
343                     final Rule.Phoneme oldPhoneme = phonemes.remove(newPhoneme);
344                     final Rule.Phoneme mergedPhoneme = oldPhoneme.mergeWithLanguage(newPhoneme.getLanguages());
345                     phonemes.put(mergedPhoneme, mergedPhoneme);
346                 } else {
347                     phonemes.put(newPhoneme, newPhoneme);
348                 }
349             });
350         });
351 
352         return new PhonemeBuilder(phonemes.keySet());
353     }
354 
355     /**
356      * Encodes a string to its phonetic representation.
357      *
358      * @param input
359      *            the String to encode
360      * @return the encoding of the input
361      */
362     public String encode(final String input) {
363         final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
364         return encode(input, languageSet);
365     }
366 
367     /**
368      * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
369      *
370      * @param input
371      *            String to phoneticise; a String with dashes or spaces separating each word
372      * @param languageSet
373      *            set of possible origin languages
374      * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations of the
375      *         input
376      */
377     public String encode(String input, final Languages.LanguageSet languageSet) {
378         final Map<String, List<Rule>> rules = Rule.getInstanceMap(this.nameType, RuleType.RULES, languageSet);
379         // rules common across many (all) languages
380         final Map<String, List<Rule>> finalRules1 = Rule.getInstanceMap(this.nameType, this.ruleType, "common");
381         // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
382         final Map<String, List<Rule>> finalRules2 = Rule.getInstanceMap(this.nameType, this.ruleType, languageSet);
383 
384         // tidy the input
385         // lower case is a locale-dependent operation
386         input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
387 
388         if (this.nameType == NameType.GENERIC) {
389             if (input.startsWith("d'")) { // check for d'
390                 final String remainder = input.substring(2);
391                 final String combined = "d" + remainder;
392                 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
393             }
394             for (final String l : NAME_PREFIXES.get(this.nameType)) {
395                 // handle generic prefixes
396                 if (input.startsWith(l + " ")) {
397                     // check for any prefix in the words list
398                     final String remainder = input.substring(l.length() + 1); // input without the prefix
399                     final String combined = l + remainder; // input with prefix without space
400                     return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
401                 }
402             }
403         }
404 
405         final List<String> words = Arrays.asList(input.split("\\s+"));
406         final List<String> words2 = new ArrayList<>();
407 
408         // special-case handling of word prefixes based upon the name type
409         switch (this.nameType) {
410         case SEPHARDIC:
411             words.forEach(aWord -> {
412                 final String[] parts = aWord.split("'", -1);
413                 words2.add(parts[parts.length - 1]);
414             });
415             words2.removeAll(NAME_PREFIXES.get(this.nameType));
416             break;
417         case ASHKENAZI:
418             words2.addAll(words);
419             words2.removeAll(NAME_PREFIXES.get(this.nameType));
420             break;
421         case GENERIC:
422             words2.addAll(words);
423             break;
424         default:
425             throw new IllegalStateException("Unreachable case: " + this.nameType);
426         }
427 
428         if (this.concat) {
429             // concat mode enabled
430             input = join(words2, " ");
431         } else if (words2.size() == 1) {
432             // not a multi-word name
433             input = words.iterator().next();
434         } else if (!words2.isEmpty()) {
435             // encode each word in a multi-word name separately (normally used for approx matches)
436             final StringBuilder result = new StringBuilder();
437             words2.forEach(word -> result.append("-").append(encode(word)));
438             // return the result without the leading "-"
439             return result.substring(1);
440         }
441 
442         PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
443 
444         // loop over each char in the input - we will handle the increment manually
445         for (int i = 0; i < input.length();) {
446             final RulesApplication rulesApplication =
447                     new RulesApplication(rules, input, phonemeBuilder, i, maxPhonemes).invoke();
448             i = rulesApplication.getI();
449             phonemeBuilder = rulesApplication.getPhonemeBuilder();
450         }
451 
452         // Apply the general rules
453         phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
454         // Apply the language-specific rules
455         phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
456 
457         return phonemeBuilder.makeString();
458     }
459 
460     /**
461      * Gets the Lang language guessing rules being used.
462      *
463      * @return the Lang in use
464      */
465     public Lang getLang() {
466         return this.lang;
467     }
468 
469     /**
470      * Gets the maximum number of phonemes the engine will calculate for a given input.
471      *
472      * @return the maximum number of phonemes
473      * @since 1.7
474      */
475     public int getMaxPhonemes() {
476         return this.maxPhonemes;
477     }
478 
479     /**
480      * Gets the NameType being used.
481      *
482      * @return the NameType in use
483      */
484     public NameType getNameType() {
485         return this.nameType;
486     }
487 
488     /**
489      * Gets the RuleType being used.
490      *
491      * @return the RuleType in use
492      */
493     public RuleType getRuleType() {
494         return this.ruleType;
495     }
496 
497     /**
498      * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
499      *
500      * @return true if multiple phonetic encodings are returned, false if just the first is
501      */
502     public boolean isConcat() {
503         return this.concat;
504     }
505 }