    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.Objects;
    031import java.util.Set;
    032import java.util.TreeMap;
    033
    034import org.apache.commons.codec.language.bm.Languages.LanguageSet;
    035import org.apache.commons.codec.language.bm.Rule.Phoneme;
    036
    037/**
    038 * Converts words into potential phonetic representations.
    039 * <p>
    040 * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
    041 * into account the likely source language. Next, this phonetic representation is converted into a
    042 * pan-European 'average' representation, allowing comparison between different versions of essentially
    043 * the same word from different languages.
    044 * <p>
    045 * This class is intentionally immutable and thread-safe.
    046 * If you wish to alter the settings for a PhoneticEngine, you
    047 * must make a new one with the updated settings.
    048 * <p>
    049 * Ported from phoneticengine.php
    050 *
    051 * @since 1.6
    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<>();
    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}.
    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<>(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} and {@code found} are updated. {@code i} points to the
    161     * index of the next char in {@code input} that must be processed next (the input up to that index having been
    162     * processed already), and {@code found} indicates if a matching rule was found or not. In the case where a
    163     * matching rule was found, {@code phonemeBuilder} 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 final 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            Objects.requireNonNull(finalRules, "finalRules");
    182            this.finalRules = finalRules;
    183            this.phonemeBuilder = phonemeBuilder;
    184            this.input = input;
    185            this.i = i;
    186            this.maxPhonemes = maxPhonemes;
    187        }
    188
    189        public int getI() {
    190            return this.i;
    191        }
    192
    193        public PhonemeBuilder getPhonemeBuilder() {
    194            return this.phonemeBuilder;
    195        }
    196
    197        /**
    198         * Invokes the rules. Loops over the rules list, stopping at the first one that has a matching context
    199         * and pattern. Then applies this rule to the phoneme builder to produce updated phonemes. If there was no
    200         * match, {@code i} is advanced one and the character is silently dropped from the phonetic spelling.
    201         *
    202         * @return {@code this}
    203         */
    204        public RulesApplication invoke() {
    205            this.found = false;
    206            int patternLength = 1;
    207            final List<Rule> rules = this.finalRules.get(input.subSequence(i, i+patternLength));
    208            if (rules != null) {
    209                for (final Rule rule : rules) {
    210                    final String pattern = rule.getPattern();
    211                    patternLength = pattern.length();
    212                    if (rule.patternAndContextMatches(this.input, this.i)) {
    213                        this.phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
    214                        this.found = true;
    215                        break;
    216                    }
    217                }
    218            }
    219
    220            if (!this.found) {
    221                patternLength = 1;
    222            }
    223
    224            this.i += patternLength;
    225            return this;
    226        }
    227
    228        public boolean isFound() {
    229            return this.found;
    230        }
    231    }
    232
    233    private static final Map<NameType, Set<String>> NAME_PREFIXES = new EnumMap<>(NameType.class);
    234
    235    static {
    236        NAME_PREFIXES.put(NameType.ASHKENAZI,
    237                Collections.unmodifiableSet(
    238                        new HashSet<>(Arrays.asList("bar", "ben", "da", "de", "van", "von"))));
    239        NAME_PREFIXES.put(NameType.SEPHARDIC,
    240                Collections.unmodifiableSet(
    241                        new HashSet<>(Arrays.asList("al", "el", "da", "dal", "de", "del", "dela", "de la",
    242                                                          "della", "des", "di", "do", "dos", "du", "van", "von"))));
    243        NAME_PREFIXES.put(NameType.GENERIC,
    244                Collections.unmodifiableSet(
    245                        new HashSet<>(Arrays.asList("da", "dal", "de", "del", "dela", "de la", "della",
    246                                                          "des", "di", "do", "dos", "du", "van", "von"))));
    247    }
    248
    249    /**
    250     * Joins some strings with an internal separator.
    251     * @param strings   Strings to join
    252     * @param sep       String to separate them with
    253     * @return a single String consisting of each element of {@code strings} interleaved by {@code sep}
    254     */
    255    private static String join(final Iterable<String> strings, final String sep) {
    256        final StringBuilder sb = new StringBuilder();
    257        final Iterator<String> si = strings.iterator();
    258        if (si.hasNext()) {
    259            sb.append(si.next());
    260        }
    261        while (si.hasNext()) {
    262            sb.append(sep).append(si.next());
    263        }
    264
    265        return sb.toString();
    266    }
    267
    268    private static final int DEFAULT_MAX_PHONEMES = 20;
    269
    270    private final Lang lang;
    271
    272    private final NameType nameType;
    273
    274    private final RuleType ruleType;
    275
    276    private final boolean concat;
    277
    278    private final int maxPhonemes;
    279
    280    /**
    281     * Generates a new, fully-configured phonetic engine.
    282     *
    283     * @param nameType
    284     *            the type of names it will use
    285     * @param ruleType
    286     *            the type of rules it will apply
    287     * @param concat
    288     *            if it will concatenate multiple encodings
    289     */
    290    public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat) {
    291        this(nameType, ruleType, concat, DEFAULT_MAX_PHONEMES);
    292    }
    293
    294    /**
    295     * Generates a new, fully-configured phonetic engine.
    296     *
    297     * @param nameType
    298     *            the type of names it will use
    299     * @param ruleType
    300     *            the type of rules it will apply
    301     * @param concat
    302     *            if it will concatenate multiple encodings
    303     * @param maxPhonemes
    304     *            the maximum number of phonemes that will be handled
    305     * @since 1.7
    306     */
    307    public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat,
    308                          final int maxPhonemes) {
    309        if (ruleType == RuleType.RULES) {
    310            throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
    311        }
    312        this.nameType = nameType;
    313        this.ruleType = ruleType;
    314        this.concat = concat;
    315        this.lang = Lang.instance(nameType);
    316        this.maxPhonemes = maxPhonemes;
    317    }
    318
    319    /**
    320     * Applies the final rules to convert from a language-specific phonetic representation to a
    321     * language-independent representation.
    322     *
    323     * @param phonemeBuilder the current phonemes
    324     * @param finalRules the final rules to apply
    325     * @return the resulting phonemes
    326     */
    327    private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder,
    328                                           final Map<String, List<Rule>> finalRules) {
    329        Objects.requireNonNull(finalRules, "finalRules");
    330        if (finalRules.isEmpty()) {
    331            return phonemeBuilder;
    332        }
    333
    334        final Map<Rule.Phoneme, Rule.Phoneme> phonemes =
    335            new TreeMap<>(Rule.Phoneme.COMPARATOR);
    336
    337        for (final Rule.Phoneme phoneme : phonemeBuilder.getPhonemes()) {
    338            PhonemeBuilder subBuilder = PhonemeBuilder.empty(phoneme.getLanguages());
    339            final String phonemeText = phoneme.getPhonemeText().toString();
    340
    341            for (int i = 0; i < phonemeText.length();) {
    342                final RulesApplication rulesApplication =
    343                        new RulesApplication(finalRules, phonemeText, subBuilder, i, maxPhonemes).invoke();
    344                final boolean found = rulesApplication.isFound();
    345                subBuilder = rulesApplication.getPhonemeBuilder();
    346
    347                if (!found) {
    348                    // not found, appending as-is
    349                    subBuilder.append(phonemeText.subSequence(i, i + 1));
    350                }
    351
    352                i = rulesApplication.getI();
    353            }
    354
    355            // the phonemes map orders the phonemes only based on their text, but ignores the language set
    356            // when adding new phonemes, check for equal phonemes and merge their language set, otherwise
    357            // phonemes with the same text but different language set get lost
    358            for (final Rule.Phoneme newPhoneme : subBuilder.getPhonemes()) {
    359                if (phonemes.containsKey(newPhoneme)) {
    360                    final Rule.Phoneme oldPhoneme = phonemes.remove(newPhoneme);
    361                    final Rule.Phoneme mergedPhoneme = oldPhoneme.mergeWithLanguage(newPhoneme.getLanguages());
    362                    phonemes.put(mergedPhoneme, mergedPhoneme);
    363                } else {
    364                    phonemes.put(newPhoneme, newPhoneme);
    365                }
    366            }
    367        }
    368
    369        return new PhonemeBuilder(phonemes.keySet());
    370    }
    371
    372    /**
    373     * Encodes a string to its phonetic representation.
    374     *
    375     * @param input
    376     *            the String to encode
    377     * @return the encoding of the input
    378     */
    379    public String encode(final String input) {
    380        final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
    381        return encode(input, languageSet);
    382    }
    383
    384    /**
    385     * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
    386     *
    387     * @param input
    388     *            String to phoneticise; a String with dashes or spaces separating each word
    389     * @param languageSet
    390     *            set of possible origin languages
    391     * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations of the
    392     *         input
    393     */
    394    public String encode(String input, final Languages.LanguageSet languageSet) {
    395        final Map<String, List<Rule>> rules = Rule.getInstanceMap(this.nameType, RuleType.RULES, languageSet);
    396        // rules common across many (all) languages
    397        final Map<String, List<Rule>> finalRules1 = Rule.getInstanceMap(this.nameType, this.ruleType, "common");
    398        // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
    399        final Map<String, List<Rule>> finalRules2 = Rule.getInstanceMap(this.nameType, this.ruleType, languageSet);
    400
    401        // tidy the input
    402        // lower case is a locale-dependent operation
    403        input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
    404
    405        if (this.nameType == NameType.GENERIC) {
    406            if (input.length() >= 2 && input.substring(0, 2).equals("d'")) { // check for d'
    407                final String remainder = input.substring(2);
    408                final String combined = "d" + remainder;
    409                return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
    410            }
    411            for (final String l : NAME_PREFIXES.get(this.nameType)) {
    412                // handle generic prefixes
    413                if (input.startsWith(l + " ")) {
    414                    // check for any prefix in the words list
    415                    final String remainder = input.substring(l.length() + 1); // input without the prefix
    416                    final String combined = l + remainder; // input with prefix without space
    417                    return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
    418                }
    419            }
    420        }
    421
    422        final List<String> words = Arrays.asList(input.split("\\s+"));
    423        final List<String> words2 = new ArrayList<>();
    424
    425        // special-case handling of word prefixes based upon the name type
    426        switch (this.nameType) {
    427        case SEPHARDIC:
    428            for (final String aWord : words) {
    429                final String[] parts = aWord.split("'");
    430                final String lastPart = parts[parts.length - 1];
    431                words2.add(lastPart);
    432            }
    433            words2.removeAll(NAME_PREFIXES.get(this.nameType));
    434            break;
    435        case ASHKENAZI:
    436            words2.addAll(words);
    437            words2.removeAll(NAME_PREFIXES.get(this.nameType));
    438            break;
    439        case GENERIC:
    440            words2.addAll(words);
    441            break;
    442        default:
    443            throw new IllegalStateException("Unreachable case: " + this.nameType);
    444        }
    445
    446        if (this.concat) {
    447            // concat mode enabled
    448            input = join(words2, " ");
    449        } else if (words2.size() == 1) {
    450            // not a multi-word name
    451            input = words.iterator().next();
    452        } else {
    453            // encode each word in a multi-word name separately (normally used for approx matches)
    454            final StringBuilder result = new StringBuilder();
    455            for (final String word : words2) {
    456                result.append("-").append(encode(word));
    457            }
    458            // return the result without the leading "-"
    459            return result.substring(1);
    460        }
    461
    462        PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
    463
    464        // loop over each char in the input - we will handle the increment manually
    465        for (int i = 0; i < input.length();) {
    466            final RulesApplication rulesApplication =
    467                    new RulesApplication(rules, input, phonemeBuilder, i, maxPhonemes).invoke();
    468            i = rulesApplication.getI();
    469            phonemeBuilder = rulesApplication.getPhonemeBuilder();
    470        }
    471
    472        // Apply the general rules
    473        phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
    474        // Apply the language-specific rules
    475        phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
    476
    477        return phonemeBuilder.makeString();
    478    }
    479
    480    /**
    481     * Gets the Lang language guessing rules being used.
    482     *
    483     * @return the Lang in use
    484     */
    485    public Lang getLang() {
    486        return this.lang;
    487    }
    488
    489    /**
    490     * Gets the NameType being used.
    491     *
    492     * @return the NameType in use
    493     */
    494    public NameType getNameType() {
    495        return this.nameType;
    496    }
    497
    498    /**
    499     * Gets the RuleType being used.
    500     *
    501     * @return the RuleType in use
    502     */
    503    public RuleType getRuleType() {
    504        return this.ruleType;
    505    }
    506
    507    /**
    508     * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
    509     *
    510     * @return true if multiple phonetic encodings are returned, false if just the first is
    511     */
    512    public boolean isConcat() {
    513        return this.concat;
    514    }
    515
    516    /**
    517     * Gets the maximum number of phonemes the engine will calculate for a given input.
    518     *
    519     * @return the maximum number of phonemes
    520     * @since 1.7
    521     */
    522    public int getMaxPhonemes() {
    523        return this.maxPhonemes;
    524    }
    525}