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; 019 020import java.util.Locale; 021 022import org.apache.commons.codec.EncoderException; 023import org.apache.commons.codec.StringEncoder; 024 025/** 026 * Encodes a string into a Cologne Phonetic value. 027 * <p> 028 * Implements the <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik">Kölner Phonetik</a> (Cologne 029 * Phonetic) algorithm issued by Hans Joachim Postel in 1969. 030 * </p> 031 * <p> 032 * The <i>Kölner Phonetik</i> is a phonetic algorithm which is optimized for the German language. It is related to 033 * the well-known soundex algorithm. 034 * </p> 035 * 036 * <h2>Algorithm</h2> 037 * 038 * <ul> 039 * 040 * <li> 041 * <h3>Step 1:</h3> 042 * After preprocessing (conversion to upper case, transcription of <a 043 * href="http://en.wikipedia.org/wiki/Germanic_umlaut">germanic umlauts</a>, removal of non alphabetical characters) the 044 * letters of the supplied text are replaced by their phonetic code according to the following table. 045 * <table border="1"> 046 * <caption style="caption-side: bottom"><small><i>(Source: <a 047 * href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik#Buchstabencodes">Wikipedia (de): Kölner Phonetik -- 048 * Buchstabencodes</a>)</i></small></caption> <tbody> 049 * <tr> 050 * <th>Letter</th> 051 * <th>Context</th> 052 * <th>Code</th> 053 * </tr> 054 * <tr> 055 * <td>A, E, I, J, O, U, Y</td> 056 * <td></td> 057 * <td>0</td> 058 * </tr> 059 * <tr> 060 * 061 * <td>H</td> 062 * <td></td> 063 * <td>-</td> 064 * </tr> 065 * <tr> 066 * <td>B</td> 067 * <td></td> 068 * <td rowspan="2">1</td> 069 * </tr> 070 * <tr> 071 * <td>P</td> 072 * <td>not before H</td> 073 * 074 * </tr> 075 * <tr> 076 * <td>D, T</td> 077 * <td>not before C, S, Z</td> 078 * <td>2</td> 079 * </tr> 080 * <tr> 081 * <td>F, V, W</td> 082 * <td></td> 083 * <td rowspan="2">3</td> 084 * </tr> 085 * <tr> 086 * 087 * <td>P</td> 088 * <td>before H</td> 089 * </tr> 090 * <tr> 091 * <td>G, K, Q</td> 092 * <td></td> 093 * <td rowspan="3">4</td> 094 * </tr> 095 * <tr> 096 * <td rowspan="2">C</td> 097 * <td>at onset before A, H, K, L, O, Q, R, U, X</td> 098 * 099 * </tr> 100 * <tr> 101 * <td>before A, H, K, O, Q, U, X except after S, Z</td> 102 * </tr> 103 * <tr> 104 * <td>X</td> 105 * <td>not after C, K, Q</td> 106 * <td>48</td> 107 * </tr> 108 * <tr> 109 * <td>L</td> 110 * <td></td> 111 * 112 * <td>5</td> 113 * </tr> 114 * <tr> 115 * <td>M, N</td> 116 * <td></td> 117 * <td>6</td> 118 * </tr> 119 * <tr> 120 * <td>R</td> 121 * <td></td> 122 * <td>7</td> 123 * </tr> 124 * 125 * <tr> 126 * <td>S, Z</td> 127 * <td></td> 128 * <td rowspan="6">8</td> 129 * </tr> 130 * <tr> 131 * <td rowspan="3">C</td> 132 * <td>after S, Z</td> 133 * </tr> 134 * <tr> 135 * <td>at onset except before A, H, K, L, O, Q, R, U, X</td> 136 * </tr> 137 * 138 * <tr> 139 * <td>not before A, H, K, O, Q, U, X</td> 140 * </tr> 141 * <tr> 142 * <td>D, T</td> 143 * <td>before C, S, Z</td> 144 * </tr> 145 * <tr> 146 * <td>X</td> 147 * <td>after C, K, Q</td> 148 * </tr> 149 * </tbody> 150 * </table> 151 * 152 * <h4>Example:</h4> 153 * 154 * <code>"M</code>ü<code>ller-L</code>ü<code>denscheidt" 155 * => "MULLERLUDENSCHEIDT" => "6005507500206880022"</code> 156 * 157 * </li> 158 * 159 * <li> 160 * <h3>Step 2:</h3> 161 * Collapse of all multiple consecutive code digits. 162 * <h4>Example:</h4> 163 * <code>"6005507500206880022" => "6050750206802"</code></li> 164 * 165 * <li> 166 * <h3>Step 3:</h3> 167 * Removal of all codes "0" except at the beginning. This means that two or more identical consecutive digits can occur 168 * if they occur after removing the "0" digits. 169 * 170 * <h4>Example:</h4> 171 * <code>"6050750206802" => "65752682"</code></li> 172 * 173 * </ul> 174 * 175 * <p> 176 * This class is thread-safe. 177 * </p> 178 * 179 * @see <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik">Wikipedia (de): Kölner Phonetik (in German)</a> 180 * @since 1.5 181 */ 182public class ColognePhonetic implements StringEncoder { 183 184 // Predefined char arrays for better performance and less GC load 185 private static final char[] AEIJOUY = new char[] { 'A', 'E', 'I', 'J', 'O', 'U', 'Y' }; 186 private static final char[] SCZ = new char[] { 'S', 'C', 'Z' }; 187 private static final char[] WFPV = new char[] { 'W', 'F', 'P', 'V' }; 188 private static final char[] GKQ = new char[] { 'G', 'K', 'Q' }; 189 private static final char[] CKQ = new char[] { 'C', 'K', 'Q' }; 190 private static final char[] AHKLOQRUX = new char[] { 'A', 'H', 'K', 'L', 'O', 'Q', 'R', 'U', 'X' }; 191 private static final char[] SZ = new char[] { 'S', 'Z' }; 192 private static final char[] AHOUKQX = new char[] { 'A', 'H', 'O', 'U', 'K', 'Q', 'X' }; 193 private static final char[] TDX = new char[] { 'T', 'D', 'X' }; 194 195 /** 196 * This class is not thread-safe; the field {@link #length} is mutable. 197 * However, it is not shared between threads, as it is constructed on demand 198 * by the method {@link ColognePhonetic#colognePhonetic(String)} 199 */ 200 private abstract class CologneBuffer { 201 202 protected final char[] data; 203 204 protected int length = 0; 205 206 public CologneBuffer(final char[] data) { 207 this.data = data; 208 this.length = data.length; 209 } 210 211 public CologneBuffer(final int buffSize) { 212 this.data = new char[buffSize]; 213 this.length = 0; 214 } 215 216 protected abstract char[] copyData(int start, final int length); 217 218 public int length() { 219 return length; 220 } 221 222 @Override 223 public String toString() { 224 return new String(copyData(0, length)); 225 } 226 } 227 228 private class CologneOutputBuffer extends CologneBuffer { 229 230 public CologneOutputBuffer(final int buffSize) { 231 super(buffSize); 232 } 233 234 public void addRight(final char chr) { 235 data[length] = chr; 236 length++; 237 } 238 239 @Override 240 protected char[] copyData(final int start, final int length) { 241 final char[] newData = new char[length]; 242 System.arraycopy(data, start, newData, 0, length); 243 return newData; 244 } 245 } 246 247 private class CologneInputBuffer extends CologneBuffer { 248 249 public CologneInputBuffer(final char[] data) { 250 super(data); 251 } 252 253 public void addLeft(final char ch) { 254 length++; 255 data[getNextPos()] = ch; 256 } 257 258 @Override 259 protected char[] copyData(final int start, final int length) { 260 final char[] newData = new char[length]; 261 System.arraycopy(data, data.length - this.length + start, newData, 0, length); 262 return newData; 263 } 264 265 public char getNextChar() { 266 return data[getNextPos()]; 267 } 268 269 protected int getNextPos() { 270 return data.length - length; 271 } 272 273 public char removeNext() { 274 final char ch = getNextChar(); 275 length--; 276 return ch; 277 } 278 } 279 280 /** 281 * Maps some Germanic characters to plain for internal processing. The following characters are mapped: 282 * <ul> 283 * <li>capital a, umlaut mark</li> 284 * <li>capital u, umlaut mark</li> 285 * <li>capital o, umlaut mark</li> 286 * <li>small sharp s, German</li> 287 * </ul> 288 */ 289 290 /* 291 * Returns whether the array contains the key, or not. 292 */ 293 private static boolean arrayContains(final char[] arr, final char key) { 294 for (final char element : arr) { 295 if (element == key) { 296 return true; 297 } 298 } 299 return false; 300 } 301 302 /** 303 * <p> 304 * Implements the <i>Kölner Phonetik</i> algorithm. 305 * </p> 306 * <p> 307 * In contrast to the initial description of the algorithm, this implementation does the encoding in one pass. 308 * </p> 309 * 310 * @param text The source text to encode 311 * @return the corresponding encoding according to the <i>Kölner Phonetik</i> algorithm 312 */ 313 public String colognePhonetic(String text) { 314 if (text == null) { 315 return null; 316 } 317 318 final CologneInputBuffer input = new CologneInputBuffer(preprocess(text)); 319 final CologneOutputBuffer output = new CologneOutputBuffer(input.length() * 2); 320 321 char nextChar; 322 323 final char CHAR_FIRST_POS = '/'; // are we processing the first character? 324 final char CHAR_IGNORE = '-'; // is this character to be ignored? 325 326 char lastChar = CHAR_IGNORE; 327 char lastCode = CHAR_FIRST_POS; 328 char code; 329 char chr; 330 331 while (input.length() > 0) { 332 chr = input.removeNext(); 333 334 if (input.length() > 0) { 335 nextChar = input.getNextChar(); 336 } else { 337 nextChar = CHAR_IGNORE; 338 } 339 340 // OK to ignore H here because it only affects nextChar which has already been set up 341 if (chr == 'H' || chr < 'A' || chr > 'Z') { 342 continue; // ignore unwanted characters 343 } 344 345 if (arrayContains(AEIJOUY, chr)) { 346 code = '0'; 347 } else if (chr == 'B' || (chr == 'P' && nextChar != 'H')) { 348 code = '1'; 349 } else if ((chr == 'D' || chr == 'T') && !arrayContains(SCZ, nextChar)) { 350 code = '2'; 351 } else if (arrayContains(WFPV, chr)) { 352 code = '3'; 353 } else if (arrayContains(GKQ, chr)) { 354 code = '4'; 355 } else if (chr == 'X' && !arrayContains(CKQ, lastChar)) { 356 code = '4'; 357 input.addLeft('S'); 358 } else if (chr == 'S' || chr == 'Z') { 359 code = '8'; 360 } else if (chr == 'C') { 361 if (lastCode == CHAR_FIRST_POS) { 362 if (arrayContains(AHKLOQRUX, nextChar)) { 363 code = '4'; 364 } else { 365 code = '8'; 366 } 367 } else { 368 if (arrayContains(SZ, lastChar) || !arrayContains(AHOUKQX, nextChar)) { 369 code = '8'; 370 } else { 371 code = '4'; 372 } 373 } 374 } else if (arrayContains(TDX, chr)) { 375 code = '8'; 376 } else if (chr == 'R') { 377 code = '7'; 378 } else if (chr == 'L') { 379 code = '5'; 380 } else if (chr == 'M' || chr == 'N') { 381 code = '6'; 382 } else { 383 code = chr; // should not happen? 384 } 385 386 if (code != CHAR_IGNORE && (lastCode != code && (code != '0' || lastCode == CHAR_FIRST_POS) || code < '0' || code > '8')) { 387 output.addRight(code); 388 } 389 390 lastChar = chr; 391 lastCode = code; 392 } 393 return output.toString(); 394 } 395 396 @Override 397 public Object encode(final Object object) throws EncoderException { 398 if (!(object instanceof String)) { 399 throw new EncoderException("This method's parameter was expected to be of the type " + 400 String.class.getName() + 401 ". But actually it was of the type " + 402 object.getClass().getName() + 403 "."); 404 } 405 return encode((String) object); 406 } 407 408 @Override 409 public String encode(final String text) { 410 return colognePhonetic(text); 411 } 412 413 public boolean isEncodeEqual(final String text1, final String text2) { 414 return colognePhonetic(text1).equals(colognePhonetic(text2)); 415 } 416 417 /** 418 * Converts the string to upper case and replaces Germanic umlaut characters 419 */ 420 private char[] preprocess(String text) { 421 // This converts German small sharp s (Eszett) to SS 422 final char[] chrs = text.toUpperCase(Locale.GERMAN).toCharArray(); 423 424 for (int index = 0; index < chrs.length; index++) { 425 switch (chrs[index]) { 426 case '\u00C4': // capital A, umlaut mark 427 chrs[index] = 'A'; 428 break; 429 case '\u00DC': // capital U, umlaut mark 430 chrs[index] = 'U'; 431 break; 432 case '\u00D6': // capital O, umlaut mark 433 chrs[index] = 'O'; 434 break; 435 default: 436 break; 437 } 438 } 439 return chrs; 440 } 441}