001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.codec.language.bm;
019
020import java.util.ArrayList;
021import java.util.Arrays;
022import java.util.Collections;
023import java.util.EnumMap;
024import java.util.HashSet;
025import java.util.Iterator;
026import java.util.LinkedHashSet;
027import java.util.List;
028import java.util.Locale;
029import java.util.Map;
030import java.util.Set;
031import java.util.TreeMap;
032
033import org.apache.commons.codec.language.bm.Languages.LanguageSet;
034import org.apache.commons.codec.language.bm.Rule.Phoneme;
035
036/**
037 * Converts words into potential phonetic representations.
038 * <p>
039 * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
040 * into account the likely source language. Next, this phonetic representation is converted into a
041 * pan-European 'average' representation, allowing comparison between different versions of essentially
042 * the same word from different languages.
043 * <p>
044 * This class is intentionally immutable and thread-safe.
045 * If you wish to alter the settings for a PhoneticEngine, you
046 * must make a new one with the updated settings.
047 * <p>
048 * Ported from phoneticengine.php
049 *
050 * @since 1.6
051 * @version $Id: PhoneticEngine.java 1634418 2014-10-27 00:43:25Z ggregory $
052 */
053public class PhoneticEngine {
054
055    /**
056     * Utility for manipulating a set of phonemes as they are being built up. Not intended for use outside
057     * this package, and probably not outside the {@link PhoneticEngine} class.
058     *
059     * @since 1.6
060     */
061    static final class PhonemeBuilder {
062
063        /**
064         * An empty builder where all phonemes must come from some set of languages. This will contain a single
065         * phoneme of zero characters. This can then be appended to. This should be the only way to create a new
066         * phoneme from scratch.
067         *
068         * @param languages the set of languages
069         * @return  a new, empty phoneme builder
070         */
071        public static PhonemeBuilder empty(final Languages.LanguageSet languages) {
072            return new PhonemeBuilder(new Rule.Phoneme("", languages));
073        }
074
075        private final Set<Rule.Phoneme> phonemes;
076
077        private PhonemeBuilder(final Rule.Phoneme phoneme) {
078            this.phonemes = new LinkedHashSet<Rule.Phoneme>();
079            this.phonemes.add(phoneme);
080        }
081
082        private PhonemeBuilder(final Set<Rule.Phoneme> phonemes) {
083            this.phonemes = phonemes;
084        }
085
086        /**
087         * Creates a new phoneme builder containing all phonemes in this one extended by <code>str</code>.
088         *
089         * @param str   the characters to append to the phonemes
090         */
091        public void append(final CharSequence str) {
092            for (final Rule.Phoneme ph : this.phonemes) {
093                ph.append(str);
094            }
095        }
096
097        /**
098         * Applies the given phoneme expression to all phonemes in this phoneme builder.
099         * <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}