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