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&ouml;lner Phonetik</a>
029 * (Cologne Phonetic) algorithm issued by Hans Joachim Postel in 1969.
030 * <p>
031 * The <i>K&ouml;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 * <caption style="caption-side: bottom"><small><i>(Source: <a href="http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik#Buchstabencodes">Wikipedia (de):
046 * K&ouml;lner Phonetik -- Buchstabencodes</a>)</i></small></caption>
047 * <tbody>
048 * <tr>
049 * <th>Letter</th>
050 * <th>Context</th>
051 * <th align="center">Code</th>
052 * </tr>
053 * <tr>
054 * <td>A, E, I, J, O, U, Y</td>
055 * <td></td>
056 * <td align="center">0</td>
057 * </tr>
058 * <tr>
059 *
060 * <td>H</td>
061 * <td></td>
062 * <td align="center">-</td>
063 * </tr>
064 * <tr>
065 * <td>B</td>
066 * <td></td>
067 * <td rowspan="2" align="center">1</td>
068 * </tr>
069 * <tr>
070 * <td>P</td>
071 * <td>not before H</td>
072 *
073 * </tr>
074 * <tr>
075 * <td>D, T</td>
076 * <td>not before C, S, Z</td>
077 * <td align="center">2</td>
078 * </tr>
079 * <tr>
080 * <td>F, V, W</td>
081 * <td></td>
082 * <td rowspan="2" align="center">3</td>
083 * </tr>
084 * <tr>
085 *
086 * <td>P</td>
087 * <td>before H</td>
088 * </tr>
089 * <tr>
090 * <td>G, K, Q</td>
091 * <td></td>
092 * <td rowspan="3" align="center">4</td>
093 * </tr>
094 * <tr>
095 * <td rowspan="2">C</td>
096 * <td>at onset before A, H, K, L, O, Q, R, U, X</td>
097 *
098 * </tr>
099 * <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 */
178public 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}