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