View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.codec.language;
19  
20  import java.util.Locale;
21  
22  import org.apache.commons.codec.EncoderException;
23  import org.apache.commons.codec.StringEncoder;
24  
25  /**
26   * Encodes a string into a Cologne Phonetic value.
27   * <p>
28   * Implements the <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik">K&ouml;lner Phonetik</a>
29   * (Cologne Phonetic) algorithm issued by Hans Joachim Postel in 1969.
30   * <p>
31   * The <i>K&ouml;lner Phonetik</i> is a phonetic algorithm which is optimized for the German language.
32   * It is related to the well-known soundex algorithm.
33   * <p>
34   *
35   * <h2>Algorithm</h2>
36   *
37   * <ul>
38   *
39   * <li>
40   * <h3>Step 1:</h3>
41   * After preprocessing (conversion to upper case, transcription of <a
42   * href="http://en.wikipedia.org/wiki/Germanic_umlaut">germanic umlauts</a>, removal of non alphabetical characters) the
43   * letters of the supplied text are replaced by their phonetic code according to the following table.
44   * <table border="1">
45   * <caption style="caption-side: bottom"><small><i>(Source: <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik#Buchstabencodes">Wikipedia (de):
46   * K&ouml;lner Phonetik -- Buchstabencodes</a>)</i></small></caption>
47   * <tbody>
48   * <tr>
49   * <th>Letter</th>
50   * <th>Context</th>
51   * <th align="center">Code</th>
52   * </tr>
53   * <tr>
54   * <td>A, E, I, J, O, U, Y</td>
55   * <td></td>
56   * <td align="center">0</td>
57   * </tr>
58   * <tr>
59   *
60   * <td>H</td>
61   * <td></td>
62   * <td align="center">-</td>
63   * </tr>
64   * <tr>
65   * <td>B</td>
66   * <td></td>
67   * <td rowspan="2" align="center">1</td>
68   * </tr>
69   * <tr>
70   * <td>P</td>
71   * <td>not before H</td>
72   *
73   * </tr>
74   * <tr>
75   * <td>D, T</td>
76   * <td>not before C, S, Z</td>
77   * <td align="center">2</td>
78   * </tr>
79   * <tr>
80   * <td>F, V, W</td>
81   * <td></td>
82   * <td rowspan="2" align="center">3</td>
83   * </tr>
84   * <tr>
85   *
86   * <td>P</td>
87   * <td>before H</td>
88   * </tr>
89   * <tr>
90   * <td>G, K, Q</td>
91   * <td></td>
92   * <td rowspan="3" align="center">4</td>
93   * </tr>
94   * <tr>
95   * <td rowspan="2">C</td>
96   * <td>at onset before A, H, K, L, O, Q, R, U, X</td>
97   *
98   * </tr>
99   * <tr>
100  * <td>before A, H, K, O, Q, U, X except after S, Z</td>
101  * </tr>
102  * <tr>
103  * <td>X</td>
104  * <td>not after C, K, Q</td>
105  * <td align="center">48</td>
106  * </tr>
107  * <tr>
108  * <td>L</td>
109  * <td></td>
110  *
111  * <td align="center">5</td>
112  * </tr>
113  * <tr>
114  * <td>M, N</td>
115  * <td></td>
116  * <td align="center">6</td>
117  * </tr>
118  * <tr>
119  * <td>R</td>
120  * <td></td>
121  * <td align="center">7</td>
122  * </tr>
123  *
124  * <tr>
125  * <td>S, Z</td>
126  * <td></td>
127  * <td rowspan="6" align="center">8</td>
128  * </tr>
129  * <tr>
130  * <td rowspan="3">C</td>
131  * <td>after S, Z</td>
132  * </tr>
133  * <tr>
134  * <td>at onset except before A, H, K, L, O, Q, R, U, X</td>
135  * </tr>
136  *
137  * <tr>
138  * <td>not before A, H, K, O, Q, U, X</td>
139  * </tr>
140  * <tr>
141  * <td>D, T</td>
142  * <td>before C, S, Z</td>
143  * </tr>
144  * <tr>
145  * <td>X</td>
146  * <td>after C, K, Q</td>
147  * </tr>
148  * </tbody>
149  * </table>
150  *
151  * <h4>Example:</h4>
152  *
153  * {@code "M}&uuml;{@code ller-L}&uuml;{@code denscheidt" => "MULLERLUDENSCHEIDT" => "6005507500206880022"}
154  *
155  * </li>
156  *
157  * <li>
158  * <h3>Step 2:</h3>
159  * Collapse of all multiple consecutive code digits.
160  * <h4>Example:</h4>
161  * {@code "6005507500206880022" => "6050750206802"}</li>
162  *
163  * <li>
164  * <h3>Step 3:</h3>
165  * Removal of all codes "0" except at the beginning. This means that two or more identical consecutive digits can occur
166  * if they occur after removing the "0" digits.
167  *
168  * <h4>Example:</h4>
169  * {@code "6050750206802" => "65752682"}</li>
170  *
171  * </ul>
172  *
173  * This class is thread-safe.
174  *
175  * @see <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik">Wikipedia (de): K&ouml;lner Phonetik (in German)</a>
176  * @since 1.5
177  */
178 public class ColognePhonetic implements StringEncoder {
179 
180     // Predefined char arrays for better performance and less GC load
181     private static final char[] AEIJOUY = new char[] { 'A', 'E', 'I', 'J', 'O', 'U', 'Y' };
182     private static final char[] SCZ = new char[] { 'S', 'C', 'Z' };
183     private static final char[] WFPV = new char[] { 'W', 'F', 'P', 'V' };
184     private static final char[] GKQ = new char[] { 'G', 'K', 'Q' };
185     private static final char[] CKQ = new char[] { 'C', 'K', 'Q' };
186     private static final char[] AHKLOQRUX = new char[] { 'A', 'H', 'K', 'L', 'O', 'Q', 'R', 'U', 'X' };
187     private static final char[] SZ = new char[] { 'S', 'Z' };
188     private static final char[] AHOUKQX = new char[] { 'A', 'H', 'O', 'U', 'K', 'Q', 'X' };
189     private static final char[] TDX = new char[] { 'T', 'D', 'X' };
190 
191     /**
192      * This class is not thread-safe; the field {@link #length} is mutable.
193      * However, it is not shared between threads, as it is constructed on demand
194      * by the method {@link ColognePhonetic#colognePhonetic(String)}
195      */
196     private abstract class CologneBuffer {
197 
198         protected final char[] data;
199 
200         protected int length = 0;
201 
202         public CologneBuffer(final char[] data) {
203             this.data = data;
204             this.length = data.length;
205         }
206 
207         public CologneBuffer(final int buffSize) {
208             this.data = new char[buffSize];
209             this.length = 0;
210         }
211 
212         protected abstract char[] copyData(int start, final int length);
213 
214         public int length() {
215             return length;
216         }
217 
218         @Override
219         public String toString() {
220             return new String(copyData(0, length));
221         }
222     }
223 
224     private class CologneOutputBuffer extends CologneBuffer {
225 
226         public CologneOutputBuffer(final int buffSize) {
227             super(buffSize);
228         }
229 
230         public void addRight(final char chr) {
231             data[length] = chr;
232             length++;
233         }
234 
235         @Override
236         protected char[] copyData(final int start, final int length) {
237             final char[] newData = new char[length];
238             System.arraycopy(data, start, newData, 0, length);
239             return newData;
240         }
241     }
242 
243     private class CologneInputBuffer extends CologneBuffer {
244 
245         public CologneInputBuffer(final char[] data) {
246             super(data);
247         }
248 
249         public void addLeft(final char ch) {
250             length++;
251             data[getNextPos()] = ch;
252         }
253 
254         @Override
255         protected char[] copyData(final int start, final int length) {
256             final char[] newData = new char[length];
257             System.arraycopy(data, data.length - this.length + start, newData, 0, length);
258             return newData;
259         }
260 
261         public char getNextChar() {
262             return data[getNextPos()];
263         }
264 
265         protected int getNextPos() {
266             return data.length - length;
267         }
268 
269         public char removeNext() {
270             final char ch = getNextChar();
271             length--;
272             return ch;
273         }
274     }
275 
276     /**
277      * Maps some Germanic characters to plain for internal processing. The following characters are mapped:
278      * <ul>
279      * <li>capital a, umlaut mark</li>
280      * <li>capital u, umlaut mark</li>
281      * <li>capital o, umlaut mark</li>
282      * <li>small sharp s, German</li>
283      * </ul>
284      */
285     private static final char[][] PREPROCESS_MAP = new char[][]{
286         {'\u00C4', 'A'}, // capital a, umlaut mark
287         {'\u00DC', 'U'}, // capital u, umlaut mark
288         {'\u00D6', 'O'}, // capital o, umlaut mark
289         {'\u00DF', 'S'} // small sharp s, German
290     };
291 
292     /*
293      * Returns whether the array contains the key, or not.
294      */
295     private static boolean arrayContains(final char[] arr, final char key) {
296         for (final char element : arr) {
297             if (element == key) {
298                 return true;
299             }
300         }
301         return false;
302     }
303 
304     /**
305      * <p>
306      * Implements the <i>K&ouml;lner Phonetik</i> algorithm.
307      * </p>
308      * <p>
309      * In contrast to the initial description of the algorithm, this implementation does the encoding in one pass.
310      * </p>
311      *
312      * @param text
313      * @return the corresponding encoding according to the <i>K&ouml;lner Phonetik</i> algorithm
314      */
315     public String colognePhonetic(String text) {
316         if (text == null) {
317             return null;
318         }
319 
320         text = preprocess(text);
321 
322         final CologneOutputBuffer output = new CologneOutputBuffer(text.length() * 2);
323         final CologneInputBuffer input = new CologneInputBuffer(text.toCharArray());
324 
325         char nextChar;
326 
327         char lastChar = '-';
328         char lastCode = '/';
329         char code;
330         char chr;
331 
332         int rightLength = input.length();
333 
334         while (rightLength > 0) {
335             chr = input.removeNext();
336 
337             if ((rightLength = input.length()) > 0) {
338                 nextChar = input.getNextChar();
339             } else {
340                 nextChar = '-';
341             }
342 
343             if (arrayContains(AEIJOUY, chr)) {
344                 code = '0';
345             } else if (chr == 'H' || chr < 'A' || chr > 'Z') {
346                 if (lastCode == '/') {
347                     continue;
348                 }
349                 code = '-';
350             } else if (chr == 'B' || (chr == 'P' && nextChar != 'H')) {
351                 code = '1';
352             } else if ((chr == 'D' || chr == 'T') && !arrayContains(SCZ, nextChar)) {
353                 code = '2';
354             } else if (arrayContains(WFPV, chr)) {
355                 code = '3';
356             } else if (arrayContains(GKQ, chr)) {
357                 code = '4';
358             } else if (chr == 'X' && !arrayContains(CKQ, lastChar)) {
359                 code = '4';
360                 input.addLeft('S');
361                 rightLength++;
362             } else if (chr == 'S' || chr == 'Z') {
363                 code = '8';
364             } else if (chr == 'C') {
365                 if (lastCode == '/') {
366                     if (arrayContains(AHKLOQRUX, nextChar)) {
367                         code = '4';
368                     } else {
369                         code = '8';
370                     }
371                 } else {
372                     if (arrayContains(SZ, lastChar) || !arrayContains(AHOUKQX, nextChar)) {
373                         code = '8';
374                     } else {
375                         code = '4';
376                     }
377                 }
378             } else if (arrayContains(TDX, chr)) {
379                 code = '8';
380             } else if (chr == 'R') {
381                 code = '7';
382             } else if (chr == 'L') {
383                 code = '5';
384             } else if (chr == 'M' || chr == 'N') {
385                 code = '6';
386             } else {
387                 code = chr;
388             }
389 
390             if (code != '-' && (lastCode != code && (code != '0' || lastCode == '/') || code < '0' || code > '8')) {
391                 output.addRight(code);
392             }
393 
394             lastChar = chr;
395             lastCode = code;
396         }
397         return output.toString();
398     }
399 
400     @Override
401     public Object encode(final Object object) throws EncoderException {
402         if (!(object instanceof String)) {
403             throw new EncoderException("This method's parameter was expected to be of the type " +
404                 String.class.getName() +
405                 ". But actually it was of the type " +
406                 object.getClass().getName() +
407                 ".");
408         }
409         return encode((String) object);
410     }
411 
412     @Override
413     public String encode(final String text) {
414         return colognePhonetic(text);
415     }
416 
417     public boolean isEncodeEqual(final String text1, final String text2) {
418         return colognePhonetic(text1).equals(colognePhonetic(text2));
419     }
420 
421     /**
422      * Converts the string to upper case and replaces germanic characters as defined in {@link #PREPROCESS_MAP}.
423      */
424     private String preprocess(String text) {
425         text = text.toUpperCase(Locale.GERMAN);
426 
427         final char[] chrs = text.toCharArray();
428 
429         for (int index = 0; index < chrs.length; index++) {
430             if (chrs[index] > 'Z') {
431                 for (final char[] element : PREPROCESS_MAP) {
432                     if (chrs[index] == element[0]) {
433                         chrs[index] = element[1];
434                         break;
435                     }
436                 }
437             }
438         }
439         return new String(chrs);
440     }
441 }