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