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