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 /**
34 * Converts words into potential phonetic representations.
35 * <p>
36 * This is a two-stage process. Firstly, the word is converted into a phonetic representation that takes
37 * into account the likely source language. Next, this phonetic representation is converted into a
38 * pan-european 'average' representation, allowing comparison between different versions of essentially
39 * the same word from different languages.
40 * <p>
41 * This class is intentionally immutable and thread-safe.
42 * If you wish to alter the settings for a PhoneticEngine, you
43 * must make a new one with the updated settings.
44 * <p>
45 * Ported from phoneticengine.php
46 *
47 * @since 1.6
48 * @version $Id: PhoneticEngine.html 889935 2013-12-11 05:05:13Z ggregory $
49 */
50 public class PhoneticEngine {
51
52 /**
53 * Utility for manipulating a set of phonemes as they are being built up. Not intended for use outside
54 * this package, and probably not outside the {@link PhoneticEngine} class.
55 *
56 * @since 1.6
57 */
58 static final class PhonemeBuilder {
59
60 /**
61 * An empty builder where all phonemes must come from some set of languages. This will contain a single
62 * phoneme of zero characters. This can then be appended to. This should be the only way to create a new
63 * phoneme from scratch.
64 *
65 * @param languages the set of languages
66 * @return a new, empty phoneme builder
67 */
68 public static PhonemeBuilder empty(final Languages.LanguageSet languages) {
69 return new PhonemeBuilder(Collections.singleton(new Rule.Phoneme("", languages)));
70 }
71
72 private final Set<Rule.Phoneme> phonemes;
73
74 private PhonemeBuilder(final Set<Rule.Phoneme> phonemes) {
75 this.phonemes = phonemes;
76 }
77
78 /**
79 * Creates a new phoneme builder containing all phonemes in this one extended by <code>str</code>.
80 *
81 * @param str the characters to append to the phonemes
82 * @return a new phoneme builder lenghtened by <code>str</code>
83 */
84 public PhonemeBuilder append(final CharSequence str) {
85 final Set<Rule.Phoneme> newPhonemes = new LinkedHashSet<Rule.Phoneme>();
86
87 for (final Rule.Phoneme ph : this.phonemes) {
88 newPhonemes.add(ph.append(str));
89 }
90
91 return new PhonemeBuilder(newPhonemes);
92 }
93
94 /**
95 * Creates a new phoneme builder containing the application of the expression to all phonemes in this builder.
96 * <p>
97 * This will lengthen phonemes that have compatible language sets to the expression, and drop those that are
98 * incompatible.
99 *
100 * @param phonemeExpr the expression to apply
101 * @param maxPhonemes the maximum number of phonemes to build up
102 * @return a new phoneme builder containing the results of <code>phonemeExpr</code> applied to each phoneme
103 * in turn
104 */
105 public PhonemeBuilder apply(final Rule.PhonemeExpr phonemeExpr, final int maxPhonemes) {
106 final Set<Rule.Phoneme> newPhonemes = new LinkedHashSet<Rule.Phoneme>();
107
108 EXPR: for (final Rule.Phoneme left : this.phonemes) {
109 for (final Rule.Phoneme right : phonemeExpr.getPhonemes()) {
110 final Rule.Phoneme join = left.join(right);
111 if (!join.getLanguages().isEmpty()) {
112 if (newPhonemes.size() < maxPhonemes) {
113 newPhonemes.add(join);
114 } else {
115 break EXPR;
116 }
117 }
118 }
119 }
120
121 return new PhonemeBuilder(newPhonemes);
122 }
123
124 /**
125 * Gets underlying phoneme set. Please don't mutate.
126 *
127 * @return the phoneme set
128 */
129 public Set<Rule.Phoneme> getPhonemes() {
130 return this.phonemes;
131 }
132
133 /**
134 * Stringifies the phoneme set. This produces a single string of the strings of each phoneme,
135 * joined with a pipe. This is explicitly provided in place of toString as it is a potentially
136 * expensive operation, which should be avoided when debugging.
137 *
138 * @return the stringified phoneme set
139 */
140 public String makeString() {
141 final StringBuilder sb = new StringBuilder();
142
143 for (final Rule.Phoneme ph : this.phonemes) {
144 if (sb.length() > 0) {
145 sb.append("|");
146 }
147 sb.append(ph.getPhonemeText());
148 }
149
150 return sb.toString();
151 }
152 }
153
154 /**
155 * A function closure capturing the application of a list of rules to an input sequence at a particular offset.
156 * After invocation, the values <code>i</code> and <code>found</code> are updated. <code>i</code> points to the
157 * index of the next char in <code>input</code> that must be processed next (the input up to that index having been
158 * processed already), and <code>found</code> indicates if a matching rule was found or not. In the case where a
159 * matching rule was found, <code>phonemeBuilder</code> is replaced with a new builder containing the phonemes
160 * updated by the matching rule.
161 *
162 * Although this class is not thread-safe (it has mutable unprotected fields), it is not shared between threads
163 * as it is constructed as needed by the calling methods.
164 * @since 1.6
165 */
166 private static final class RulesApplication {
167 private final List<Rule> finalRules;
168 private final CharSequence input;
169
170 private PhonemeBuilder phonemeBuilder;
171 private int i;
172 private final int maxPhonemes;
173 private boolean found;
174
175 public RulesApplication(final List<Rule> finalRules, final CharSequence input,
176 final PhonemeBuilder phonemeBuilder, final int i, final int maxPhonemes) {
177 if (finalRules == null) {
178 throw new NullPointerException("The finalRules argument must not be null");
179 }
180 this.finalRules = finalRules;
181 this.phonemeBuilder = phonemeBuilder;
182 this.input = input;
183 this.i = i;
184 this.maxPhonemes = maxPhonemes;
185 }
186
187 public int getI() {
188 return this.i;
189 }
190
191 public PhonemeBuilder getPhonemeBuilder() {
192 return this.phonemeBuilder;
193 }
194
195 /**
196 * Invokes the rules. Loops over the rules list, stopping at the first one that has a matching context
197 * and pattern. Then applies this rule to the phoneme builder to produce updated phonemes. If there was no
198 * match, <code>i</code> is advanced one and the character is silently dropped from the phonetic spelling.
199 *
200 * @return <code>this</code>
201 */
202 public RulesApplication invoke() {
203 this.found = false;
204 int patternLength = 0;
205 for (final Rule rule : this.finalRules) {
206 final String pattern = rule.getPattern();
207 patternLength = pattern.length();
208
209 if (!rule.patternAndContextMatches(this.input, this.i)) {
210 continue;
211 }
212
213 this.phonemeBuilder = this.phonemeBuilder.apply(rule.getPhoneme(), maxPhonemes);
214 this.found = true;
215 break;
216 }
217
218 if (!this.found) {
219 patternLength = 1;
220 }
221
222 this.i += patternLength;
223 return this;
224 }
225
226 public boolean isFound() {
227 return this.found;
228 }
229 }
230
231 private static final Map<NameType, Set<String>> NAME_PREFIXES = new EnumMap<NameType, Set<String>>(NameType.class);
232
233 static {
234 NAME_PREFIXES.put(NameType.ASHKENAZI,
235 Collections.unmodifiableSet(
236 new HashSet<String>(Arrays.asList("bar", "ben", "da", "de", "van", "von"))));
237 NAME_PREFIXES.put(NameType.SEPHARDIC,
238 Collections.unmodifiableSet(
239 new HashSet<String>(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<String>(Arrays.asList("da", "dal", "de", "del", "dela", "de la", "della",
244 "des", "di", "do", "dos", "du", "van", "von"))));
245 }
246
247 /**
248 * This is a performance hack to avoid overhead associated with very frequent CharSequence.subSequence calls.
249 *
250 * @param cached the character sequence to cache
251 * @return a <code>CharSequence</code> that internally caches subSequence values
252 */
253 private static CharSequence cacheSubSequence(final CharSequence cached) {
254 // return cached;
255 final CharSequence[][] cache = new CharSequence[cached.length()][cached.length()];
256 return new CharSequence() {
257 @Override
258 public char charAt(final int index) {
259 return cached.charAt(index);
260 }
261
262 @Override
263 public int length() {
264 return cached.length();
265 }
266
267 @Override
268 public CharSequence subSequence(final int start, final int end) {
269 if (start == end) {
270 return "";
271 }
272
273 CharSequence res = cache[start][end - 1];
274 if (res == null) {
275 res = cached.subSequence(start, end);
276 cache[start][end - 1] = res;
277 }
278 return res;
279 }
280 };
281 }
282
283 /**
284 * Joins some strings with an internal separator.
285 * @param strings Strings to join
286 * @param sep String to separate them with
287 * @return a single String consisting of each element of <code>strings</code> interleaved by <code>sep</code>
288 */
289 private static String join(final Iterable<String> strings, final String sep) {
290 final StringBuilder sb = new StringBuilder();
291 final Iterator<String> si = strings.iterator();
292 if (si.hasNext()) {
293 sb.append(si.next());
294 }
295 while (si.hasNext()) {
296 sb.append(sep).append(si.next());
297 }
298
299 return sb.toString();
300 }
301
302 private static final int DEFAULT_MAX_PHONEMES = 20;
303
304 private final Lang lang;
305
306 private final NameType nameType;
307
308 private final RuleType ruleType;
309
310 private final boolean concat;
311
312 private final int maxPhonemes;
313
314 /**
315 * Generates a new, fully-configured phonetic engine.
316 *
317 * @param nameType
318 * the type of names it will use
319 * @param ruleType
320 * the type of rules it will apply
321 * @param concat
322 * if it will concatenate multiple encodings
323 */
324 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat) {
325 this(nameType, ruleType, concat, DEFAULT_MAX_PHONEMES);
326 }
327
328 /**
329 * Generates a new, fully-configured phonetic engine.
330 *
331 * @param nameType
332 * the type of names it will use
333 * @param ruleType
334 * the type of rules it will apply
335 * @param concat
336 * if it will concatenate multiple encodings
337 * @param maxPhonemes
338 * the maximum number of phonemes that will be handled
339 * @since 1.7
340 */
341 public PhoneticEngine(final NameType nameType, final RuleType ruleType, final boolean concat,
342 final int maxPhonemes) {
343 if (ruleType == RuleType.RULES) {
344 throw new IllegalArgumentException("ruleType must not be " + RuleType.RULES);
345 }
346 this.nameType = nameType;
347 this.ruleType = ruleType;
348 this.concat = concat;
349 this.lang = Lang.instance(nameType);
350 this.maxPhonemes = maxPhonemes;
351 }
352
353 /**
354 * Applies the final rules to convert from a language-specific phonetic representation to a
355 * language-independent representation.
356 *
357 * @param phonemeBuilder the current phonemes
358 * @param finalRules the final rules to apply
359 * @return the resulting phonemes
360 */
361 private PhonemeBuilder applyFinalRules(final PhonemeBuilder phonemeBuilder, final List<Rule> finalRules) {
362 if (finalRules == null) {
363 throw new NullPointerException("finalRules can not be null");
364 }
365 if (finalRules.isEmpty()) {
366 return phonemeBuilder;
367 }
368
369 final Set<Rule.Phoneme> phonemes = new TreeSet<Rule.Phoneme>(Rule.Phoneme.COMPARATOR);
370
371 for (final Rule.Phoneme phoneme : phonemeBuilder.getPhonemes()) {
372 PhonemeBuilder subBuilder = PhonemeBuilder.empty(phoneme.getLanguages());
373 final CharSequence phonemeText = cacheSubSequence(phoneme.getPhonemeText());
374
375 for (int i = 0; i < phonemeText.length();) {
376 final RulesApplication rulesApplication =
377 new RulesApplication(finalRules, phonemeText, subBuilder, i, maxPhonemes).invoke();
378 final boolean found = rulesApplication.isFound();
379 subBuilder = rulesApplication.getPhonemeBuilder();
380
381 if (!found) {
382 // not found, appending as-is
383 subBuilder = subBuilder.append(phonemeText.subSequence(i, i + 1));
384 }
385
386 i = rulesApplication.getI();
387 }
388
389 phonemes.addAll(subBuilder.getPhonemes());
390 }
391
392 return new PhonemeBuilder(phonemes);
393 }
394
395 /**
396 * Encodes a string to its phonetic representation.
397 *
398 * @param input
399 * the String to encode
400 * @return the encoding of the input
401 */
402 public String encode(final String input) {
403 final Languages.LanguageSet languageSet = this.lang.guessLanguages(input);
404 return encode(input, languageSet);
405 }
406
407 /**
408 * Encodes an input string into an output phonetic representation, given a set of possible origin languages.
409 *
410 * @param input
411 * String to phoneticise; a String with dashes or spaces separating each word
412 * @param languageSet
413 * @return a phonetic representation of the input; a String containing '-'-separated phonetic representations
414 * of the input
415 */
416 public String encode(String input, final Languages.LanguageSet languageSet) {
417 final List<Rule> rules = Rule.getInstance(this.nameType, RuleType.RULES, languageSet);
418 // rules common across many (all) languages
419 final List<Rule> finalRules1 = Rule.getInstance(this.nameType, this.ruleType, "common");
420 // rules that apply to a specific language that may be ambiguous or wrong if applied to other languages
421 final List<Rule> finalRules2 = Rule.getInstance(this.nameType, this.ruleType, languageSet);
422
423 // tidy the input
424 // lower case is a locale-dependent operation
425 input = input.toLowerCase(Locale.ENGLISH).replace('-', ' ').trim();
426
427 if (this.nameType == NameType.GENERIC) {
428 if (input.length() >= 2 && input.substring(0, 2).equals("d'")) { // check for d'
429 final String remainder = input.substring(2);
430 final String combined = "d" + remainder;
431 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
432 }
433 for (final String l : NAME_PREFIXES.get(this.nameType)) {
434 // handle generic prefixes
435 if (input.startsWith(l + " ")) {
436 // check for any prefix in the words list
437 final String remainder = input.substring(l.length() + 1); // input without the prefix
438 final String combined = l + remainder; // input with prefix without space
439 return "(" + encode(remainder) + ")-(" + encode(combined) + ")";
440 }
441 }
442 }
443
444 final List<String> words = Arrays.asList(input.split("\\s+"));
445 final List<String> words2 = new ArrayList<String>();
446
447 // special-case handling of word prefixes based upon the name type
448 switch (this.nameType) {
449 case SEPHARDIC:
450 for (final String aWord : words) {
451 final String[] parts = aWord.split("'");
452 final String lastPart = parts[parts.length - 1];
453 words2.add(lastPart);
454 }
455 words2.removeAll(NAME_PREFIXES.get(this.nameType));
456 break;
457 case ASHKENAZI:
458 words2.addAll(words);
459 words2.removeAll(NAME_PREFIXES.get(this.nameType));
460 break;
461 case GENERIC:
462 words2.addAll(words);
463 break;
464 default:
465 throw new IllegalStateException("Unreachable case: " + this.nameType);
466 }
467
468 if (this.concat) {
469 // concat mode enabled
470 input = join(words2, " ");
471 } else if (words2.size() == 1) {
472 // not a multi-word name
473 input = words.iterator().next();
474 } else {
475 // encode each word in a multi-word name separately (normally used for approx matches)
476 final StringBuilder result = new StringBuilder();
477 for (final String word : words2) {
478 result.append("-").append(encode(word));
479 }
480 // return the result without the leading "-"
481 return result.substring(1);
482 }
483
484 PhonemeBuilder phonemeBuilder = PhonemeBuilder.empty(languageSet);
485
486 // loop over each char in the input - we will handle the increment manually
487 final CharSequence inputCache = cacheSubSequence(input);
488 for (int i = 0; i < inputCache.length();) {
489 final RulesApplication rulesApplication =
490 new RulesApplication(rules, inputCache, phonemeBuilder, i, maxPhonemes).invoke();
491 i = rulesApplication.getI();
492 phonemeBuilder = rulesApplication.getPhonemeBuilder();
493 }
494
495 // Apply the general rules
496 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules1);
497 // Apply the language-specific rules
498 phonemeBuilder = applyFinalRules(phonemeBuilder, finalRules2);
499
500 return phonemeBuilder.makeString();
501 }
502
503 /**
504 * Gets the Lang language guessing rules being used.
505 *
506 * @return the Lang in use
507 */
508 public Lang getLang() {
509 return this.lang;
510 }
511
512 /**
513 * Gets the NameType being used.
514 *
515 * @return the NameType in use
516 */
517 public NameType getNameType() {
518 return this.nameType;
519 }
520
521 /**
522 * Gets the RuleType being used.
523 *
524 * @return the RuleType in use
525 */
526 public RuleType getRuleType() {
527 return this.ruleType;
528 }
529
530 /**
531 * Gets if multiple phonetic encodings are concatenated or if just the first one is kept.
532 *
533 * @return true if multiple phonetic encodings are returned, false if just the first is
534 */
535 public boolean isConcat() {
536 return this.concat;
537 }
538
539 /**
540 * Gets the maximum number of phonemes the engine will calculate for a given input.
541 *
542 * @return the maximum number of phonemes
543 * @since 1.7
544 */
545 public int getMaxPhonemes() {
546 return this.maxPhonemes;
547 }
548 }