1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.codec.language.bm;
19
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collections;
23 import java.util.EnumMap;
24 import java.util.HashSet;
25 import java.util.Iterator;
26 import java.util.LinkedHashSet;
27 import java.util.List;
28 import java.util.Locale;
29 import java.util.Map;
30 import java.util.Set;
31 import java.util.TreeSet;
32
33 import org.apache.commons.codec.language.bm.Languages.LanguageSet;
34 import org.apache.commons.codec.language.bm.Rule.Phoneme;
35
36 /**
37 * Converts words into potential phonetic representations.
38 * <p>
39 * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
40 * into account the likely source language. Next, this phonetic representation is converted into a
41 * pan-European 'average' representation, allowing comparison between different versions of essentially
42 * the same word from different languages.
43 * <p>
44 * This class is intentionally immutable and thread-safe.
45 * If you wish to alter the settings for a PhoneticEngine, you
46 * must make a new one with the updated settings.
47 * <p>
48 * Ported from phoneticengine.php
49 *
50 * @since 1.6
51 * @version $Id: PhoneticEngine.html 891688 2013-12-24 20:49:46Z ggregory $
52 */
53 public class PhoneticEngine {
54
55 /**
56 * Utility for manipulating a set of phonemes as they are being built up. Not intended for use outside
57 * this package, and probably not outside the {@link PhoneticEngine} class.
58 *
59 * @since 1.6
60 */
61 static final class PhonemeBuilder {
62
63 /**
64 * An empty builder where all phonemes must come from some set of languages. This will contain a single
65 * phoneme of zero characters. This can then be appended to. This should be the only way to create a new
66 * phoneme from scratch.
67 *
68 * @param languages the set of languages
69 * @return a new, empty phoneme builder
70 */
71 public static PhonemeBuilder empty(final Languages.LanguageSet languages) {
72 return new PhonemeBuilder(new Rule.Phoneme("", languages));
73 }
74
75 private final Set<Rule.Phoneme> phonemes;
76
77 private PhonemeBuilder(final Rule.Phoneme phoneme) {
78 this.phonemes = new LinkedHashSet<Rule.Phoneme>();
79 this.phonemes.add(phoneme);
80 }
81
82 private PhonemeBuilder(final Set<Rule.Phoneme> phonemes) {
83 this.phonemes = phonemes;
84 }
85
86 /**
87 * Creates a new phoneme builder containing all phonemes in this one extended by <code>str</code>.
88 *
89 * @param str the characters to append to the phonemes
90 */
91 public void append(final CharSequence str) {
92 for (final Rule.Phoneme ph : this.phonemes) {
93 ph.append(str);
94 }
95 }
96
97 /**
98 * Applies the given phoneme expression to all phonemes in this phoneme builder.
99 * <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<Rule.Phoneme>(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</code> and <code>found</code> are updated. <code>i</code> points to the
161 * index of the next char in <code>input</code> that must be processed next (the input up to that index having been
162 * processed already), and <code>found</code> indicates if a matching rule was found or not. In the case where a
163 * matching rule was found, <code>phonemeBuilder</code> 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 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 if (finalRules == null) {
182 throw new NullPointerException("The finalRules argument must not be null");
183 }
184 this.finalRules = finalRules;
185 this.phonemeBuilder = phonemeBuilder;
186 this.input = input;
187 this.i = i;
188 this.maxPhonemes = maxPhonemes;
189 }
190
191 public int getI() {
192 return this.i;
193 }
194
195 public PhonemeBuilder getPhonemeBuilder() {
196 return this.phonemeBuilder;
197 }
198
199 /**
200 * Invokes the rules. Loops over the rules list, stopping at the first one that has a matching context
201 * and pattern. Then applies this rule to the phoneme builder to produce updated phonemes. If there was no
202 * match, <code>i</code> is advanced one and the character is silently dropped from the phonetic spelling.
203 *
204 * @return <code>this</code>
205 */
206 public RulesApplication invoke() {
207 this.found = false;
208 int patternLength = 1;
209 final List<Rule> rules = this.finalRules.get(input.subSequence(i, i+patternLength));
210 if (rules != null) {
211 for (final Rule rule : rules) {
212 final String pattern = rule.getPattern();
213 patternLength = pattern.length();
214 if (rule.patternAndContextMatches(this.input, this.i)) {
215 this.phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
216 this.found = true;
217 break;
218 }
219 }
220 }
221
222 if (!this.found) {
223 patternLength = 1;
224 }
225
226 this.i += patternLength;
227 return this;
228 }
229
230 public boolean isFound() {
231 return this.found;
232 }
233 }
234
235 private static final Map<NameType, Set<String>> NAME_PREFIXES = new EnumMap<NameType, Set<String>>(NameType.class);
236
237 static {
238 NAME_PREFIXES.put(NameType.ASHKENAZI,
239 Collections.unmodifiableSet(
240 new HashSet<String>(Arrays.asList("bar", "ben", "da", "de", "van", "von"))));
241 NAME_PREFIXES.put(NameType.SEPHARDIC,
242 Collections.unmodifiableSet(
243 new HashSet<String>(Arrays.asList("al", "el", "da", "dal", "de", "del", "dela", "de la",
244 "della", "des", "di", "do", "dos", "du", "van", "von"))));
245 NAME_PREFIXES.put(NameType.GENERIC,
246 Collections.unmodifiableSet(
247 new HashSet<String>(Arrays.asList("da", "dal", "de", "del", "dela", "de la", "della",
248 "des", "di", "do", "dos", "du", "van", "von"))));
249 }
250
251 /**
252 * Joins some strings with an internal separator.
253 * @param strings Strings to join
254 * @param sep String to separate them with
255 * @return a single String consisting of each element of <code>strings</code> interleaved by <code>sep</code>
256 */
257 private static String join(final Iterable<String> strings, final String sep) {
258 final StringBuilder sb = new StringBuilder();
259 final Iterator<String> si = strings.iterator();
260 if (si.hasNext()) {
261 sb.append(si.next());
262 }
263 while (si.hasNext()) {
264 sb.append(sep).append(si.next());
265 }
266
267 return sb.toString();
268 }
269
270 private static final int DEFAULT_MAX_PHONEMES = 20;
271
272 private final Lang lang;
273
274 private final NameType nameType;
275
276 private final RuleType ruleType;
277
278 private final boolean concat;
279
280 private final int maxPhonemes;
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 concat
290 * if it will concatenate multiple encodings
291 */
292 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat) {
293 this(nameType, ruleType, concat, DEFAULT_MAX_PHONEMES);
294 }
295
296 /**
297 * Generates a new, fully-configured phonetic engine.
298 *
299 * @param nameType
300 * the type of names it will use
301 * @param ruleType
302 * the type of rules it will apply
303 * @param concat
304 * if it will concatenate multiple encodings
305 * @param maxPhonemes
306 * the maximum number of phonemes that will be handled
307 * @since 1.7
308 */
309 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat,
310 final int maxPhonemes) {
311 if (ruleType == RuleType.RULES) {
312 throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
313 }
314 this.nameType = nameType;
315 this.ruleType = ruleType;
316 this.concat = concat;
317 this.lang = Lang.instance(nameType);
318 this.maxPhonemes = maxPhonemes;
319 }
320
321 /**
322 * Applies the final rules to convert from a language-specific phonetic representation to a
323 * language-independent representation.
324 *
325 * @param phonemeBuilder the current phonemes
326 * @param finalRules the final rules to apply
327 * @return the resulting phonemes
328 */
329 private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder,
330 final Map<String, List<Rule>> finalRules) {
331 if (finalRules == null) {
332 throw new NullPointerException("finalRules can not be null");
333 }
334 if (finalRules.isEmpty()) {
335 return phonemeBuilder;
336 }
337
338 final Set<Rule.Phoneme> phonemes = new TreeSet<Rule.Phoneme>(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 phonemes.addAll(subBuilder.getPhonemes());
359 }
360
361 return new PhonemeBuilder(phonemes);
362 }
363
364 /**
365 * Encodes a string to its phonetic representation.
366 *
367 * @param input
368 * the String to encode
369 * @return the encoding of the input
370 */
371 public String encode(final String input) {
372 final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
373 return encode(input, languageSet);
374 }
375
376 /**
377 * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
378 *
379 * @param input
380 * String to phoneticise; a String with dashes or spaces separating each word
381 * @param languageSet
382 * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations
383 * of the input
384 */
385 public String encode(String input, final Languages.LanguageSet languageSet) {
386 final Map<String, List<Rule>> rules = Rule.getInstanceMap(this.nameType, RuleType.RULES, languageSet);
387 // rules common across many (all) languages
388 final Map<String, List<Rule>> finalRules1 = Rule.getInstanceMap(this.nameType, this.ruleType, "common");
389 // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
390 final Map<String, List<Rule>> finalRules2 = Rule.getInstanceMap(this.nameType, this.ruleType, languageSet);
391
392 // tidy the input
393 // lower case is a locale-dependent operation
394 input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
395
396 if (this.nameType == NameType.GENERIC) {
397 if (input.length() >= 2 && input.substring(0, 2).equals("d'")) { // check for d'
398 final String remainder = input.substring(2);
399 final String combined = "d" + remainder;
400 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
401 }
402 for (final String l : NAME_PREFIXES.get(this.nameType)) {
403 // handle generic prefixes
404 if (input.startsWith(l + " ")) {
405 // check for any prefix in the words list
406 final String remainder = input.substring(l.length() + 1); // input without the prefix
407 final String combined = l + remainder; // input with prefix without space
408 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
409 }
410 }
411 }
412
413 final List<String> words = Arrays.asList(input.split("\\s+"));
414 final List<String> words2 = new ArrayList<String>();
415
416 // special-case handling of word prefixes based upon the name type
417 switch (this.nameType) {
418 case SEPHARDIC:
419 for (final String aWord : words) {
420 final String[] parts = aWord.split("'");
421 final String lastPart = parts[parts.length - 1];
422 words2.add(lastPart);
423 }
424 words2.removeAll(NAME_PREFIXES.get(this.nameType));
425 break;
426 case ASHKENAZI:
427 words2.addAll(words);
428 words2.removeAll(NAME_PREFIXES.get(this.nameType));
429 break;
430 case GENERIC:
431 words2.addAll(words);
432 break;
433 default:
434 throw new IllegalStateException("Unreachable case: " + this.nameType);
435 }
436
437 if (this.concat) {
438 // concat mode enabled
439 input = join(words2, " ");
440 } else if (words2.size() == 1) {
441 // not a multi-word name
442 input = words.iterator().next();
443 } else {
444 // encode each word in a multi-word name separately (normally used for approx matches)
445 final StringBuilder result = new StringBuilder();
446 for (final String word : words2) {
447 result.append("-").append(encode(word));
448 }
449 // return the result without the leading "-"
450 return result.substring(1);
451 }
452
453 PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
454
455 // loop over each char in the input - we will handle the increment manually
456 for (int i = 0; i < input.length();) {
457 final RulesApplication rulesApplication =
458 new RulesApplication(rules, input, phonemeBuilder, i, maxPhonemes).invoke();
459 i = rulesApplication.getI();
460 phonemeBuilder = rulesApplication.getPhonemeBuilder();
461 }
462
463 // Apply the general rules
464 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
465 // Apply the language-specific rules
466 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
467
468 return phonemeBuilder.makeString();
469 }
470
471 /**
472 * Gets the Lang language guessing rules being used.
473 *
474 * @return the Lang in use
475 */
476 public Lang getLang() {
477 return this.lang;
478 }
479
480 /**
481 * Gets the NameType being used.
482 *
483 * @return the NameType in use
484 */
485 public NameType getNameType() {
486 return this.nameType;
487 }
488
489 /**
490 * Gets the RuleType being used.
491 *
492 * @return the RuleType in use
493 */
494 public RuleType getRuleType() {
495 return this.ruleType;
496 }
497
498 /**
499 * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
500 *
501 * @return true if multiple phonetic encodings are returned, false if just the first is
502 */
503 public boolean isConcat() {
504 return this.concat;
505 }
506
507 /**
508 * Gets the maximum number of phonemes the engine will calculate for a given input.
509 *
510 * @return the maximum number of phonemes
511 * @since 1.7
512 */
513 public int getMaxPhonemes() {
514 return this.maxPhonemes;
515 }
516 }