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