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}