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