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