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 */ 017package org.apache.commons.codec.language; 018 019import java.io.InputStream; 020import java.util.ArrayList; 021import java.util.Arrays; 022import java.util.Collections; 023import java.util.Comparator; 024import java.util.HashMap; 025import java.util.LinkedHashSet; 026import java.util.List; 027import java.util.Map; 028import java.util.Scanner; 029import java.util.Set; 030 031import org.apache.commons.codec.CharEncoding; 032import org.apache.commons.codec.EncoderException; 033import org.apache.commons.codec.StringEncoder; 034 035/** 036 * Encodes a string into a Daitch-Mokotoff Soundex value. 037 * <p> 038 * The Daitch-Mokotoff Soundex algorithm is a refinement of the Russel and American Soundex algorithms, yielding greater 039 * accuracy in matching especially Slavish and Yiddish surnames with similar pronunciation but differences in spelling. 040 * </p> 041 * <p> 042 * The main differences compared to the other soundex variants are: 043 * </p> 044 * <ul> 045 * <li>coded names are 6 digits long 046 * <li>the initial character of the name is coded 047 * <li>rules to encoded multi-character n-grams 048 * <li>multiple possible encodings for the same name (branching) 049 * </ul> 050 * <p> 051 * This implementation supports branching, depending on the used method: 052 * <ul> 053 * <li>{@link #encode(String)} - branching disabled, only the first code will be returned 054 * <li>{@link #soundex(String)} - branching enabled, all codes will be returned, separated by '|' 055 * </ul> 056 * <p> 057 * Note: this implementation has additional branching rules compared to the original description of the algorithm. The 058 * rules can be customized by overriding the default rules contained in the resource file 059 * {@code org/apache/commons/codec/language/dmrules.txt}. 060 * </p> 061 * <p> 062 * This class is thread-safe. 063 * </p> 064 * 065 * @see Soundex 066 * @see <a href="http://en.wikipedia.org/wiki/Daitch%E2%80%93Mokotoff_Soundex"> Wikipedia - Daitch-Mokotoff Soundex</a> 067 * @see <a href="http://www.avotaynu.com/soundex.htm">Avotaynu - Soundexing and Genealogy</a> 068 * 069 * @version $Id$ 070 * @since 1.10 071 */ 072public class DaitchMokotoffSoundex implements StringEncoder { 073 074 /** 075 * Inner class representing a branch during DM soundex encoding. 076 */ 077 private static final class Branch { 078 private final StringBuilder builder; 079 private String cachedString; 080 private String lastReplacement; 081 082 private Branch() { 083 builder = new StringBuilder(); 084 lastReplacement = null; 085 cachedString = null; 086 } 087 088 /** 089 * Creates a new branch, identical to this branch. 090 * 091 * @return a new, identical branch 092 */ 093 public Branch createBranch() { 094 final Branch branch = new Branch(); 095 branch.builder.append(toString()); 096 branch.lastReplacement = this.lastReplacement; 097 return branch; 098 } 099 100 @Override 101 public boolean equals(final Object other) { 102 if (this == other) { 103 return true; 104 } 105 if (!(other instanceof Branch)) { 106 return false; 107 } 108 109 return toString().equals(((Branch) other).toString()); 110 } 111 112 /** 113 * Finish this branch by appending '0's until the maximum code length has been reached. 114 */ 115 public void finish() { 116 while (builder.length() < MAX_LENGTH) { 117 builder.append('0'); 118 cachedString = null; 119 } 120 } 121 122 @Override 123 public int hashCode() { 124 return toString().hashCode(); 125 } 126 127 /** 128 * Process the next replacement to be added to this branch. 129 * 130 * @param replacement 131 * the next replacement to append 132 * @param forceAppend 133 * indicates if the default processing shall be overridden 134 */ 135 public void processNextReplacement(final String replacement, final boolean forceAppend) { 136 final boolean append = lastReplacement == null || !lastReplacement.endsWith(replacement) || forceAppend; 137 138 if (append && builder.length() < MAX_LENGTH) { 139 builder.append(replacement); 140 // remove all characters after the maximum length 141 if (builder.length() > MAX_LENGTH) { 142 builder.delete(MAX_LENGTH, builder.length()); 143 } 144 cachedString = null; 145 } 146 147 lastReplacement = replacement; 148 } 149 150 @Override 151 public String toString() { 152 if (cachedString == null) { 153 cachedString = builder.toString(); 154 } 155 return cachedString; 156 } 157 } 158 159 /** 160 * Inner class for storing rules. 161 */ 162 private static final class Rule { 163 private final String pattern; 164 private final String[] replacementAtStart; 165 private final String[] replacementBeforeVowel; 166 private final String[] replacementDefault; 167 168 protected Rule(final String pattern, final String replacementAtStart, final String replacementBeforeVowel, 169 final String replacementDefault) { 170 this.pattern = pattern; 171 this.replacementAtStart = replacementAtStart.split("\\|"); 172 this.replacementBeforeVowel = replacementBeforeVowel.split("\\|"); 173 this.replacementDefault = replacementDefault.split("\\|"); 174 } 175 176 public int getPatternLength() { 177 return pattern.length(); 178 } 179 180 public String[] getReplacements(final String context, final boolean atStart) { 181 if (atStart) { 182 return replacementAtStart; 183 } 184 185 final int nextIndex = getPatternLength(); 186 final boolean nextCharIsVowel = nextIndex < context.length() ? isVowel(context.charAt(nextIndex)) : false; 187 if (nextCharIsVowel) { 188 return replacementBeforeVowel; 189 } 190 191 return replacementDefault; 192 } 193 194 private boolean isVowel(final char ch) { 195 return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; 196 } 197 198 public boolean matches(final String context) { 199 return context.startsWith(pattern); 200 } 201 202 @Override 203 public String toString() { 204 return String.format("%s=(%s,%s,%s)", pattern, Arrays.asList(replacementAtStart), 205 Arrays.asList(replacementBeforeVowel), Arrays.asList(replacementDefault)); 206 } 207 } 208 209 private static final String COMMENT = "//"; 210 private static final String DOUBLE_QUOTE = "\""; 211 212 private static final String MULTILINE_COMMENT_END = "*/"; 213 214 private static final String MULTILINE_COMMENT_START = "/*"; 215 216 /** The resource file containing the replacement and folding rules */ 217 private static final String RESOURCE_FILE = "org/apache/commons/codec/language/dmrules.txt"; 218 219 /** The code length of a DM soundex value. */ 220 private static final int MAX_LENGTH = 6; 221 222 /** Transformation rules indexed by the first character of their pattern. */ 223 private static final Map<Character, List<Rule>> RULES = new HashMap<>(); 224 225 /** Folding rules. */ 226 private static final Map<Character, Character> FOLDINGS = new HashMap<>(); 227 228 static { 229 final InputStream rulesIS = DaitchMokotoffSoundex.class.getClassLoader().getResourceAsStream(RESOURCE_FILE); 230 if (rulesIS == null) { 231 throw new IllegalArgumentException("Unable to load resource: " + RESOURCE_FILE); 232 } 233 234 try (final Scanner scanner = new Scanner(rulesIS, CharEncoding.UTF_8)) { 235 parseRules(scanner, RESOURCE_FILE, RULES, FOLDINGS); 236 } 237 238 // sort RULES by pattern length in descending order 239 for (final Map.Entry<Character, List<Rule>> rule : RULES.entrySet()) { 240 final List<Rule> ruleList = rule.getValue(); 241 Collections.sort(ruleList, new Comparator<Rule>() { 242 @Override 243 public int compare(final Rule rule1, final Rule rule2) { 244 return rule2.getPatternLength() - rule1.getPatternLength(); 245 } 246 }); 247 } 248 } 249 250 private static void parseRules(final Scanner scanner, final String location, 251 final Map<Character, List<Rule>> ruleMapping, final Map<Character, Character> asciiFoldings) { 252 int currentLine = 0; 253 boolean inMultilineComment = false; 254 255 while (scanner.hasNextLine()) { 256 currentLine++; 257 final String rawLine = scanner.nextLine(); 258 String line = rawLine; 259 260 if (inMultilineComment) { 261 if (line.endsWith(MULTILINE_COMMENT_END)) { 262 inMultilineComment = false; 263 } 264 continue; 265 } 266 267 if (line.startsWith(MULTILINE_COMMENT_START)) { 268 inMultilineComment = true; 269 } else { 270 // discard comments 271 final int cmtI = line.indexOf(COMMENT); 272 if (cmtI >= 0) { 273 line = line.substring(0, cmtI); 274 } 275 276 // trim leading-trailing whitespace 277 line = line.trim(); 278 279 if (line.length() == 0) { 280 continue; // empty lines can be safely skipped 281 } 282 283 if (line.contains("=")) { 284 // folding 285 final String[] parts = line.split("="); 286 if (parts.length != 2) { 287 throw new IllegalArgumentException("Malformed folding statement split into " + parts.length + 288 " parts: " + rawLine + " in " + location); 289 } 290 final String leftCharacter = parts[0]; 291 final String rightCharacter = parts[1]; 292 293 if (leftCharacter.length() != 1 || rightCharacter.length() != 1) { 294 throw new IllegalArgumentException("Malformed folding statement - " + 295 "patterns are not single characters: " + rawLine + " in " + location); 296 } 297 298 asciiFoldings.put(leftCharacter.charAt(0), rightCharacter.charAt(0)); 299 } else { 300 // rule 301 final String[] parts = line.split("\\s+"); 302 if (parts.length != 4) { 303 throw new IllegalArgumentException("Malformed rule statement split into " + parts.length + 304 " parts: " + rawLine + " in " + location); 305 } 306 try { 307 final String pattern = stripQuotes(parts[0]); 308 final String replacement1 = stripQuotes(parts[1]); 309 final String replacement2 = stripQuotes(parts[2]); 310 final String replacement3 = stripQuotes(parts[3]); 311 312 final Rule r = new Rule(pattern, replacement1, replacement2, replacement3); 313 final char patternKey = r.pattern.charAt(0); 314 List<Rule> rules = ruleMapping.get(patternKey); 315 if (rules == null) { 316 rules = new ArrayList<>(); 317 ruleMapping.put(patternKey, rules); 318 } 319 rules.add(r); 320 } catch (final IllegalArgumentException e) { 321 throw new IllegalStateException( 322 "Problem parsing line '" + currentLine + "' in " + location, e); 323 } 324 } 325 } 326 } 327 } 328 329 private static String stripQuotes(String str) { 330 if (str.startsWith(DOUBLE_QUOTE)) { 331 str = str.substring(1); 332 } 333 334 if (str.endsWith(DOUBLE_QUOTE)) { 335 str = str.substring(0, str.length() - 1); 336 } 337 338 return str; 339 } 340 341 /** Whether to use ASCII folding prior to encoding. */ 342 private final boolean folding; 343 344 /** 345 * Creates a new instance with ASCII-folding enabled. 346 */ 347 public DaitchMokotoffSoundex() { 348 this(true); 349 } 350 351 /** 352 * Creates a new instance. 353 * <p> 354 * With ASCII-folding enabled, certain accented characters will be transformed to equivalent ASCII characters, e.g. 355 * รจ -> e. 356 * </p> 357 * 358 * @param folding 359 * if ASCII-folding shall be performed before encoding 360 */ 361 public DaitchMokotoffSoundex(final boolean folding) { 362 this.folding = folding; 363 } 364 365 /** 366 * Performs a cleanup of the input string before the actual soundex transformation. 367 * <p> 368 * Removes all whitespace characters and performs ASCII folding if enabled. 369 * </p> 370 * 371 * @param input 372 * the input string to cleanup 373 * @return a cleaned up string 374 */ 375 private String cleanup(final String input) { 376 final StringBuilder sb = new StringBuilder(); 377 for (char ch : input.toCharArray()) { 378 if (Character.isWhitespace(ch)) { 379 continue; 380 } 381 382 ch = Character.toLowerCase(ch); 383 if (folding && FOLDINGS.containsKey(ch)) { 384 ch = FOLDINGS.get(ch); 385 } 386 sb.append(ch); 387 } 388 return sb.toString(); 389 } 390 391 /** 392 * Encodes an Object using the Daitch-Mokotoff soundex algorithm without branching. 393 * <p> 394 * This method is provided in order to satisfy the requirements of the Encoder interface, and will throw an 395 * EncoderException if the supplied object is not of type java.lang.String. 396 * </p> 397 * 398 * @see #soundex(String) 399 * 400 * @param obj 401 * Object to encode 402 * @return An object (of type java.lang.String) containing the DM soundex code, which corresponds to the String 403 * supplied. 404 * @throws EncoderException 405 * if the parameter supplied is not of type java.lang.String 406 * @throws IllegalArgumentException 407 * if a character is not mapped 408 */ 409 @Override 410 public Object encode(final Object obj) throws EncoderException { 411 if (!(obj instanceof String)) { 412 throw new EncoderException( 413 "Parameter supplied to DaitchMokotoffSoundex encode is not of type java.lang.String"); 414 } 415 return encode((String) obj); 416 } 417 418 /** 419 * Encodes a String using the Daitch-Mokotoff soundex algorithm without branching. 420 * 421 * @see #soundex(String) 422 * 423 * @param source 424 * A String object to encode 425 * @return A DM Soundex code corresponding to the String supplied 426 * @throws IllegalArgumentException 427 * if a character is not mapped 428 */ 429 @Override 430 public String encode(final String source) { 431 if (source == null) { 432 return null; 433 } 434 return soundex(source, false)[0]; 435 } 436 437 /** 438 * Encodes a String using the Daitch-Mokotoff soundex algorithm with branching. 439 * <p> 440 * In case a string is encoded into multiple codes (see branching rules), the result will contain all codes, 441 * separated by '|'. 442 * </p> 443 * <p> 444 * Example: the name "AUERBACH" is encoded as both 445 * </p> 446 * <ul> 447 * <li>097400</li> 448 * <li>097500</li> 449 * </ul> 450 * <p> 451 * Thus the result will be "097400|097500". 452 * </p> 453 * 454 * @param source 455 * A String object to encode 456 * @return A string containing a set of DM Soundex codes corresponding to the String supplied 457 * @throws IllegalArgumentException 458 * if a character is not mapped 459 */ 460 public String soundex(final String source) { 461 final String[] branches = soundex(source, true); 462 final StringBuilder sb = new StringBuilder(); 463 int index = 0; 464 for (final String branch : branches) { 465 sb.append(branch); 466 if (++index < branches.length) { 467 sb.append('|'); 468 } 469 } 470 return sb.toString(); 471 } 472 473 /** 474 * Perform the actual DM Soundex algorithm on the input string. 475 * 476 * @param source 477 * A String object to encode 478 * @param branching 479 * If branching shall be performed 480 * @return A string array containing all DM Soundex codes corresponding to the String supplied depending on the 481 * selected branching mode 482 */ 483 private String[] soundex(final String source, final boolean branching) { 484 if (source == null) { 485 return null; 486 } 487 488 final String input = cleanup(source); 489 490 final Set<Branch> currentBranches = new LinkedHashSet<>(); 491 currentBranches.add(new Branch()); 492 493 char lastChar = '\0'; 494 for (int index = 0; index < input.length(); index++) { 495 final char ch = input.charAt(index); 496 497 // ignore whitespace inside a name 498 if (Character.isWhitespace(ch)) { 499 continue; 500 } 501 502 final String inputContext = input.substring(index); 503 final List<Rule> rules = RULES.get(ch); 504 if (rules == null) { 505 continue; 506 } 507 508 // use an EMPTY_LIST to avoid false positive warnings wrt potential null pointer access 509 @SuppressWarnings("unchecked") 510 final List<Branch> nextBranches = branching ? new ArrayList<Branch>() : Collections.EMPTY_LIST; 511 512 for (final Rule rule : rules) { 513 if (rule.matches(inputContext)) { 514 if (branching) { 515 nextBranches.clear(); 516 } 517 final String[] replacements = rule.getReplacements(inputContext, lastChar == '\0'); 518 final boolean branchingRequired = replacements.length > 1 && branching; 519 520 for (final Branch branch : currentBranches) { 521 for (final String nextReplacement : replacements) { 522 // if we have multiple replacements, always create a new branch 523 final Branch nextBranch = branchingRequired ? branch.createBranch() : branch; 524 525 // special rule: occurrences of mn or nm are treated differently 526 final boolean force = (lastChar == 'm' && ch == 'n') || (lastChar == 'n' && ch == 'm'); 527 528 nextBranch.processNextReplacement(nextReplacement, force); 529 530 if (branching) { 531 nextBranches.add(nextBranch); 532 } else { 533 break; 534 } 535 } 536 } 537 538 if (branching) { 539 currentBranches.clear(); 540 currentBranches.addAll(nextBranches); 541 } 542 index += rule.getPatternLength() - 1; 543 break; 544 } 545 } 546 547 lastChar = ch; 548 } 549 550 final String[] result = new String[currentBranches.size()]; 551 int index = 0; 552 for (final Branch branch : currentBranches) { 553 branch.finish(); 554 result[index++] = branch.toString(); 555 } 556 557 return result; 558 } 559}