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