    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
    018    package org.apache.commons.codec.language.bm;
    019
    020    import java.util.ArrayList;
    021    import java.util.Arrays;
    022    import java.util.Collections;
    023    import java.util.EnumMap;
    024    import java.util.HashSet;
    025    import java.util.Iterator;
    026    import java.util.LinkedHashSet;
    027    import java.util.List;
    028    import java.util.Locale;
    029    import java.util.Map;
    030    import java.util.Set;
    031    import java.util.TreeSet;
    032
    033    /**
    034     * Converts words into potential phonetic representations.
    035     * <p>
    036     * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
    037     * into account the likely source language. Next, this phonetic representation is converted into a
    038     * pan-european 'average' representation, allowing comparison between different versions of essentially
    039     * the same word from different languages.
    040     * <p>
    041     * This class is intentionally immutable and thread-safe.
    042     * If you wish to alter the settings for a PhoneticEngine, you
    043     * must make a new one with the updated settings.
    044     * <p>
    045     * Ported from phoneticengine.php
    046     *
    047     * @since 1.6
    048     * @version $Id: PhoneticEngine.java 1465848 2013-04-09 00:41:12Z sebb $
    049     */
    050    public class PhoneticEngine {
    051
    052        /**
    053         * Utility for manipulating a set of phonemes as they are being built up. Not intended for use outside
    054         * this package, and probably not outside the {@link PhoneticEngine} class.
    055         *
    056         * @since 1.6
    057         */
    058        static final class PhonemeBuilder {
    059
    060            /**
    061             * An empty builder where all phonemes must come from some set of languages. This will contain a single
    062             * phoneme of zero characters. This can then be appended to. This should be the only way to create a new
    063             * phoneme from scratch.
    064             *
    065             * @param languages the set of languages
    066             * @return  a new, empty phoneme builder
    067             */
    068            public static PhonemeBuilder empty(final Languages.LanguageSet languages) {
    069                return new PhonemeBuilder(Collections.singleton(new Rule.Phoneme("", languages)));
    070            }
    071
    072            private final Set<Rule.Phoneme> phonemes;
    073
    074            private PhonemeBuilder(final Set<Rule.Phoneme> phonemes) {
    075                this.phonemes = phonemes;
    076            }
    077
    078            /**
    079             * Creates a new phoneme builder containing all phonemes in this one extended by <code>str</code>.
    080             *
    081             * @param str   the characters to append to the phonemes
    082             * @return  a new phoneme builder lenghtened by <code>str</code>
    083             */
    084            public PhonemeBuilder append(final CharSequence str) {
    085                final Set<Rule.Phoneme> newPhonemes = new LinkedHashSet<Rule.Phoneme>();
    086
    087                for (final Rule.Phoneme ph : this.phonemes) {
    088                    newPhonemes.add(ph.append(str));
    089                }
    090
    091                return new PhonemeBuilder(newPhonemes);
    092            }
    093
    094            /**
    095             * Creates a new phoneme builder containing the application of the expression to all phonemes in this builder.
    096             * <p>
    097             * This will lengthen phonemes that have compatible language sets to the expression, and drop those that are
    098             * incompatible.
    099             *
    100             * @param phonemeExpr   the expression to apply
    101             * @param maxPhonemes   the maximum number of phonemes to build up
    102             * @return  a new phoneme builder containing the results of <code>phonemeExpr</code> applied to each phoneme
    103             *      in turn
    104             */
    105            public PhonemeBuilder apply(final Rule.PhonemeExpr phonemeExpr, final int maxPhonemes) {
    106                final Set<Rule.Phoneme> newPhonemes = new LinkedHashSet<Rule.Phoneme>();
    107
    108                EXPR: for (final Rule.Phoneme left : this.phonemes) {
    109                    for (final Rule.Phoneme right : phonemeExpr.getPhonemes()) {
    110                        final Rule.Phoneme join = left.join(right);
    111                        if (!join.getLanguages().isEmpty()) {
    112                            if (newPhonemes.size() < maxPhonemes) {
    113                                newPhonemes.add(join);
    114                            } else {
    115                                break EXPR;
    116                            }
    117                        }
    118                    }
    119                }
    120
    121                return new PhonemeBuilder(newPhonemes);
    122            }
    123
    124            /**
    125             * Gets underlying phoneme set. Please don't mutate.
    126             *
    127             * @return  the phoneme set
    128             */
    129            public Set<Rule.Phoneme> getPhonemes() {
    130                return this.phonemes;
    131            }
    132
    133            /**
    134             * Stringifies the phoneme set. This produces a single string of the strings of each phoneme,
    135             * joined with a pipe. This is explicitly provided in place of toString as it is a potentially
    136             * expensive operation, which should be avoided when debugging.
    137             *
    138             * @return  the stringified phoneme set
    139             */
    140            public String makeString() {
    141                final StringBuilder sb = new StringBuilder();
    142
    143                for (final Rule.Phoneme ph : this.phonemes) {
    144                    if (sb.length() > 0) {
    145                        sb.append("|");
    146                    }
    147                    sb.append(ph.getPhonemeText());
    148                }
    149
    150                return sb.toString();
    151            }
    152        }
    153
    154        /**
    155         * A function closure capturing the application of a list of rules to an input sequence at a particular offset.
    156         * After invocation, the values <code>i</code> and <code>found</code> are updated. <code>i</code> points to the
    157         * index of the next char in <code>input</code> that must be processed next (the input up to that index having been
    158         * processed already), and <code>found</code> indicates if a matching rule was found or not. In the case where a
    159         * matching rule was found, <code>phonemeBuilder</code> is replaced with a new builder containing the phonemes
    160         * updated by the matching rule.
    161         *
    162         * Although this class is not thread-safe (it has mutable unprotected fields), it is not shared between threads
    163         * as it is constructed as needed by the calling methods.
    164         * @since 1.6
    165         */
    166        private static final class RulesApplication {
    167            private final List<Rule> finalRules;
    168            private final CharSequence input;
    169
    170            private PhonemeBuilder phonemeBuilder;
    171            private int i;
    172            private final int maxPhonemes;
    173            private boolean found;
    174
    175            public RulesApplication(final List<Rule> finalRules, final CharSequence input,
    176                                    final PhonemeBuilder phonemeBuilder, final int i, final int maxPhonemes) {
    177                if (finalRules == null) {
    178                    throw new NullPointerException("The finalRules argument must not be null");
    179                }
    180                this.finalRules = finalRules;
    181                this.phonemeBuilder = phonemeBuilder;
    182                this.input = input;
    183                this.i = i;
    184                this.maxPhonemes = maxPhonemes;
    185            }
    186
    187            public int getI() {
    188                return this.i;
    189            }
    190
    191            public PhonemeBuilder getPhonemeBuilder() {
    192                return this.phonemeBuilder;
    193            }
    194
    195            /**
    196             * Invokes the rules. Loops over the rules list, stopping at the first one that has a matching context
    197             * and pattern. Then applies this rule to the phoneme builder to produce updated phonemes. If there was no
    198             * match, <code>i</code> is advanced one and the character is silently dropped from the phonetic spelling.
    199             *
    200             * @return <code>this</code>
    201             */
    202            public RulesApplication invoke() {
    203                this.found = false;
    204                int patternLength = 0;
    205                for (final Rule rule : this.finalRules) {
    206                    final String pattern = rule.getPattern();
    207                    patternLength = pattern.length();
    208
    209                    if (!rule.patternAndContextMatches(this.input, this.i)) {
    210                        continue;
    211                    }
    212
    213                    this.phonemeBuilder = this.phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
    214                    this.found = true;
    215                    break;
    216                }
    217
    218                if (!this.found) {
    219                    patternLength = 1;
    220                }
    221
    222                this.i += patternLength;
    223                return this;
    224            }
    225
    226            public boolean isFound() {
    227                return this.found;
    228            }
    229        }
    230
    231        private static final Map<NameType, Set<String>> NAME_PREFIXES = new EnumMap<NameType, Set<String>>(NameType.class);
    232
    233        static {
    234            NAME_PREFIXES.put(NameType.ASHKENAZI,
    235                    Collections.unmodifiableSet(
    236                            new HashSet<String>(Arrays.asList("bar", "ben", "da", "de", "van", "von"))));
    237            NAME_PREFIXES.put(NameType.SEPHARDIC,
    238                    Collections.unmodifiableSet(
    239                            new HashSet<String>(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<String>(Arrays.asList("da", "dal", "de", "del", "dela", "de la", "della",
    244                                                              "des", "di", "do", "dos", "du", "van", "von"))));
    245        }
    246
    247        /**
    248         * This is a performance hack to avoid overhead associated with very frequent CharSequence.subSequence calls.
    249         *
    250         * @param cached the character sequence to cache
    251         * @return a <code>CharSequence</code> that internally caches subSequence values
    252         */
    253        private static CharSequence cacheSubSequence(final CharSequence cached) {
    254            // return cached;
    255            final CharSequence[][] cache = new CharSequence[cached.length()][cached.length()];
    256            return new CharSequence() {
    257                @Override
    258                public char charAt(final int index) {
    259                    return cached.charAt(index);
    260                }
    261
    262                @Override
    263                public int length() {
    264                    return cached.length();
    265                }
    266
    267                @Override
    268                public CharSequence subSequence(final int start, final int end) {
    269                    if (start == end) {
    270                        return "";
    271                    }
    272
    273                    CharSequence res = cache[start][end - 1];
    274                    if (res == null) {
    275                        res = cached.subSequence(start, end);
    276                        cache[start][end - 1] = res;
    277                    }
    278                    return res;
    279                }
    280            };
    281        }
    282
    283        /**
    284         * Joins some strings with an internal separator.
    285         * @param strings   Strings to join
    286         * @param sep       String to separate them with
    287         * @return a single String consisting of each element of <code>strings</code> interleaved by <code>sep</code>
    288         */
    289        private static String join(final Iterable<String> strings, final String sep) {
    290            final StringBuilder sb = new StringBuilder();
    291            final Iterator<String> si = strings.iterator();
    292            if (si.hasNext()) {
    293                sb.append(si.next());
    294            }
    295            while (si.hasNext()) {
    296                sb.append(sep).append(si.next());
    297            }
    298
    299            return sb.toString();
    300        }
    301
    302        private static final int DEFAULT_MAX_PHONEMES = 20;
    303
    304        private final Lang lang;
    305
    306        private final NameType nameType;
    307
    308        private final RuleType ruleType;
    309
    310        private final boolean concat;
    311
    312        private final int maxPhonemes;
    313
    314        /**
    315         * Generates a new, fully-configured phonetic engine.
    316         *
    317         * @param nameType
    318         *            the type of names it will use
    319         * @param ruleType
    320         *            the type of rules it will apply
    321         * @param concat
    322         *            if it will concatenate multiple encodings
    323         */
    324        public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat) {
    325            this(nameType, ruleType, concat, DEFAULT_MAX_PHONEMES);
    326        }
    327
    328        /**
    329         * Generates a new, fully-configured phonetic engine.
    330         *
    331         * @param nameType
    332         *            the type of names it will use
    333         * @param ruleType
    334         *            the type of rules it will apply
    335         * @param concat
    336         *            if it will concatenate multiple encodings
    337         * @param maxPhonemes
    338         *            the maximum number of phonemes that will be handled
    339         * @since 1.7
    340         */
    341        public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat,
    342                              final int maxPhonemes) {
    343            if (ruleType == RuleType.RULES) {
    344                throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
    345            }
    346            this.nameType = nameType;
    347            this.ruleType = ruleType;
    348            this.concat = concat;
    349            this.lang = Lang.instance(nameType);
    350            this.maxPhonemes = maxPhonemes;
    351        }
    352
    353        /**
    354         * Applies the final rules to convert from a language-specific phonetic representation to a
    355         * language-independent representation.
    356         *
    357         * @param phonemeBuilder the current phonemes
    358         * @param finalRules the final rules to apply
    359         * @return the resulting phonemes
    360         */
    361        private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder, final List<Rule> finalRules) {
    362            if (finalRules == null) {
    363                throw new NullPointerException("finalRules can not be null");
    364            }
    365            if (finalRules.isEmpty()) {
    366                return phonemeBuilder;
    367            }
    368
    369            final Set<Rule.Phoneme> phonemes = new TreeSet<Rule.Phoneme>(Rule.Phoneme.COMPARATOR);
    370
    371            for (final Rule.Phoneme phoneme : phonemeBuilder.getPhonemes()) {
    372                PhonemeBuilder subBuilder = PhonemeBuilder.empty(phoneme.getLanguages());
    373                final CharSequence phonemeText = cacheSubSequence(phoneme.getPhonemeText());
    374
    375                for (int i = 0; i < phonemeText.length();) {
    376                    final RulesApplication rulesApplication =
    377                            new RulesApplication(finalRules, phonemeText, subBuilder, i, maxPhonemes).invoke();
    378                    final boolean found = rulesApplication.isFound();
    379                    subBuilder = rulesApplication.getPhonemeBuilder();
    380
    381                    if (!found) {
    382                        // not found, appending as-is
    383                        subBuilder = subBuilder.append(phonemeText.subSequence(i, i + 1));
    384                    }
    385
    386                    i = rulesApplication.getI();
    387                }
    388
    389                phonemes.addAll(subBuilder.getPhonemes());
    390            }
    391
    392            return new PhonemeBuilder(phonemes);
    393        }
    394
    395        /**
    396         * Encodes a string to its phonetic representation.
    397         *
    398         * @param input
    399         *            the String to encode
    400         * @return the encoding of the input
    401         */
    402        public String encode(final String input) {
    403            final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
    404            return encode(input, languageSet);
    405        }
    406
    407        /**
    408         * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
    409         *
    410         * @param input
    411         *            String to phoneticise; a String with dashes or spaces separating each word
    412         * @param languageSet
    413         * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations
    414         *   of the input
    415         */
    416        public String encode(String input, final Languages.LanguageSet languageSet) {
    417            final List<Rule> rules = Rule.getInstance(this.nameType, RuleType.RULES, languageSet);
    418            // rules common across many (all) languages
    419            final List<Rule> finalRules1 = Rule.getInstance(this.nameType, this.ruleType, "common");
    420            // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
    421            final List<Rule> finalRules2 = Rule.getInstance(this.nameType, this.ruleType, languageSet);
    422
    423            // tidy the input
    424            // lower case is a locale-dependent operation
    425            input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
    426
    427            if (this.nameType == NameType.GENERIC) {
    428                if (input.length() >= 2 && input.substring(0, 2).equals("d'")) { // check for d'
    429                    final String remainder = input.substring(2);
    430                    final String combined = "d" + remainder;
    431                    return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
    432                }
    433                for (final String l : NAME_PREFIXES.get(this.nameType)) {
    434                    // handle generic prefixes
    435                    if (input.startsWith(l + " ")) {
    436                        // check for any prefix in the words list
    437                        final String remainder = input.substring(l.length() + 1); // input without the prefix
    438                        final String combined = l + remainder; // input with prefix without space
    439                        return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
    440                    }
    441                }
    442            }
    443
    444            final List<String> words = Arrays.asList(input.split("\\s+"));
    445            final List<String> words2 = new ArrayList<String>();
    446
    447            // special-case handling of word prefixes based upon the name type
    448            switch (this.nameType) {
    449            case SEPHARDIC:
    450                for (final String aWord : words) {
    451                    final String[] parts = aWord.split("'");
    452                    final String lastPart = parts[parts.length - 1];
    453                    words2.add(lastPart);
    454                }
    455                words2.removeAll(NAME_PREFIXES.get(this.nameType));
    456                break;
    457            case ASHKENAZI:
    458                words2.addAll(words);
    459                words2.removeAll(NAME_PREFIXES.get(this.nameType));
    460                break;
    461            case GENERIC:
    462                words2.addAll(words);
    463                break;
    464            default:
    465                throw new IllegalStateException("Unreachable case: " + this.nameType);
    466            }
    467
    468            if (this.concat) {
    469                // concat mode enabled
    470                input = join(words2, " ");
    471            } else if (words2.size() == 1) {
    472                // not a multi-word name
    473                input = words.iterator().next();
    474            } else {
    475                // encode each word in a multi-word name separately (normally used for approx matches)
    476                final StringBuilder result = new StringBuilder();
    477                for (final String word : words2) {
    478                    result.append("-").append(encode(word));
    479                }
    480                // return the result without the leading "-"
    481                return result.substring(1);
    482            }
    483
    484            PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
    485
    486            // loop over each char in the input - we will handle the increment manually
    487            final CharSequence inputCache = cacheSubSequence(input);
    488            for (int i = 0; i < inputCache.length();) {
    489                final RulesApplication rulesApplication =
    490                        new RulesApplication(rules, inputCache, phonemeBuilder, i, maxPhonemes).invoke();
    491                i = rulesApplication.getI();
    492                phonemeBuilder = rulesApplication.getPhonemeBuilder();
    493            }
    494
    495            // Apply the general rules
    496            phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
    497            // Apply the language-specific rules
    498            phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
    499
    500            return phonemeBuilder.makeString();
    501        }
    502
    503        /**
    504         * Gets the Lang language guessing rules being used.
    505         *
    506         * @return the Lang in use
    507         */
    508        public Lang getLang() {
    509            return this.lang;
    510        }
    511
    512        /**
    513         * Gets the NameType being used.
    514         *
    515         * @return the NameType in use
    516         */
    517        public NameType getNameType() {
    518            return this.nameType;
    519        }
    520
    521        /**
    522         * Gets the RuleType being used.
    523         *
    524         * @return the RuleType in use
    525         */
    526        public RuleType getRuleType() {
    527            return this.ruleType;
    528        }
    529
    530        /**
    531         * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
    532         *
    533         * @return true if multiple phonetic encodings are returned, false if just the first is
    534         */
    535        public boolean isConcat() {
    536            return this.concat;
    537        }
    538
    539        /**
    540         * Gets the maximum number of phonemes the engine will calculate for a given input.
    541         *
    542         * @return the maximum number of phonemes
    543         * @since 1.7
    544         */
    545        public int getMaxPhonemes() {
    546            return this.maxPhonemes;
    547        }
    548    }