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> (Cologne
029 * Phonetic) algorithm issued by Hans Joachim Postel in 1969.
030 * </p>
031 * <p>
032 * The <i>K&ouml;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&ouml;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>&uuml;<code>ller-L</code>&uuml;<code>denscheidt"
155 * =&gt; "MULLERLUDENSCHEIDT" =&gt; "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" =&gt; "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" =&gt; "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&ouml;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[] CSZ = new char[] { 'C', 'S', 'Z' };
187    private static final char[] FPVW = new char[] { 'F', 'P', 'V', 'W' };
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[] AHKOQUX = new char[] { 'A', 'H', 'K', 'O', 'Q', 'U', 'X' };
193    private static final char[] DTX = new char[] { 'D', 'T', 'X' };
194
195    private static final char CHAR_IGNORE = '-';    // is this character to be ignored?
196
197    /**
198     * This class is not thread-safe; the field {@link #length} is mutable.
199     * However, it is not shared between threads, as it is constructed on demand
200     * by the method {@link ColognePhonetic#colognePhonetic(String)}
201     */
202    private abstract class CologneBuffer {
203
204        protected final char[] data;
205
206        protected int length = 0;
207
208        public CologneBuffer(final char[] data) {
209            this.data = data;
210            this.length = data.length;
211        }
212
213        public CologneBuffer(final int buffSize) {
214            this.data = new char[buffSize];
215            this.length = 0;
216        }
217
218        protected abstract char[] copyData(int start, final int length);
219
220        public int length() {
221            return length;
222        }
223
224        @Override
225        public String toString() {
226            return new String(copyData(0, length));
227        }
228    }
229
230    private class CologneOutputBuffer extends CologneBuffer {
231
232        private char lastCode;
233
234        public CologneOutputBuffer(final int buffSize) {
235            super(buffSize);
236            lastCode = '/'; // impossible value
237        }
238
239        /**
240         * Store the next code in the output buffer, keeping track of the previous code.
241         * '0' is only stored if it is the first entry.
242         * Ignored chars are never stored.
243         * If the code is the same as the last code (whether stored or not) it is not stored.
244         */
245        public void put(final char code) {
246            if (code != CHAR_IGNORE && lastCode != code && (code != '0' || length == 0)) {
247                data[length] = code;
248                length++;
249            }
250            lastCode = code;
251        }
252
253        @Override
254        protected char[] copyData(final int start, final int length) {
255            final char[] newData = new char[length];
256            System.arraycopy(data, start, newData, 0, length);
257            return newData;
258        }
259    }
260
261    private class CologneInputBuffer extends CologneBuffer {
262
263        public CologneInputBuffer(final char[] data) {
264            super(data);
265        }
266
267        @Override
268        protected char[] copyData(final int start, final int length) {
269            final char[] newData = new char[length];
270            System.arraycopy(data, data.length - this.length + start, newData, 0, length);
271            return newData;
272        }
273
274        public char getNextChar() {
275            return data[getNextPos()];
276        }
277
278        protected int getNextPos() {
279            return data.length - length;
280        }
281
282        public char removeNext() {
283            final char ch = getNextChar();
284            length--;
285            return ch;
286        }
287    }
288
289    /*
290     * Returns whether the array contains the key, or not.
291     */
292    private static boolean arrayContains(final char[] arr, final char key) {
293        for (final char element : arr) {
294            if (element == key) {
295                return true;
296            }
297        }
298        return false;
299    }
300
301    /**
302     * <p>
303     * Implements the <i>K&ouml;lner Phonetik</i> algorithm.
304     * </p>
305     * <p>
306     * In contrast to the initial description of the algorithm, this implementation does the encoding in one pass.
307     * </p>
308     *
309     * @param text The source text to encode
310     * @return the corresponding encoding according to the <i>K&ouml;lner Phonetik</i> algorithm
311     */
312    public String colognePhonetic(final String text) {
313        if (text == null) {
314            return null;
315        }
316
317        final CologneInputBuffer input = new CologneInputBuffer(preprocess(text));
318        final CologneOutputBuffer output = new CologneOutputBuffer(input.length() * 2);
319
320        char nextChar;
321
322        char lastChar = CHAR_IGNORE;
323        char chr;
324
325        while (input.length() > 0) {
326            chr = input.removeNext();
327
328            if (input.length() > 0) {
329                nextChar = input.getNextChar();
330            } else {
331                nextChar = CHAR_IGNORE;
332            }
333
334            if (chr < 'A' || chr > 'Z') {
335                    continue; // ignore unwanted characters
336            }
337
338            if (arrayContains(AEIJOUY, chr)) {
339                output.put('0');
340            } else if (chr == 'B' || (chr == 'P' && nextChar != 'H')) {
341                output.put('1');
342            } else if ((chr == 'D' || chr == 'T') && !arrayContains(CSZ, nextChar)) {
343                output.put('2');
344            } else if (arrayContains(FPVW, chr)) {
345                output.put('3');
346            } else if (arrayContains(GKQ, chr)) {
347                output.put('4');
348            } else if (chr == 'X' && !arrayContains(CKQ, lastChar)) {
349                output.put('4');
350                output.put('8');
351            } else if (chr == 'S' || chr == 'Z') {
352                output.put('8');
353            } else if (chr == 'C') {
354                if (output.length() == 0) {
355                    if (arrayContains(AHKLOQRUX, nextChar)) {
356                        output.put('4');
357                    } else {
358                        output.put('8');
359                    }
360                } else {
361                    if (arrayContains(SZ, lastChar) || !arrayContains(AHKOQUX, nextChar)) {
362                        output.put('8');
363                    } else {
364                        output.put('4');
365                    }
366                }
367            } else if (arrayContains(DTX, chr)) {
368                output.put('8');
369            } else if (chr == 'R') {
370                output.put('7');
371            } else if (chr == 'L') {
372                output.put('5');
373            } else if (chr == 'M' || chr == 'N') {
374                output.put('6');
375            } else if (chr == 'H') {
376                output.put(CHAR_IGNORE); // needed by put
377            } else {
378                // ignored; should not happen
379            }
380
381            lastChar = chr;
382        }
383        return output.toString();
384    }
385
386    @Override
387    public Object encode(final Object object) throws EncoderException {
388        if (!(object instanceof String)) {
389            throw new EncoderException("This method's parameter was expected to be of the type " +
390                String.class.getName() +
391                ". But actually it was of the type " +
392                object.getClass().getName() +
393                ".");
394        }
395        return encode((String) object);
396    }
397
398    @Override
399    public String encode(final String text) {
400        return colognePhonetic(text);
401    }
402
403    public boolean isEncodeEqual(final String text1, final String text2) {
404        return colognePhonetic(text1).equals(colognePhonetic(text2));
405    }
406
407    /**
408     * Converts the string to upper case and replaces Germanic umlaut characters
409     * The following characters are mapped:
410     * <ul>
411     * <li>capital A, umlaut mark</li>
412     * <li>capital U, umlaut mark</li>
413     * <li>capital O, umlaut mark</li>
414     * <li>small sharp s, German</li>
415     * </ul>
416     */
417    private char[] preprocess(final String text) {
418        // This converts German small sharp s (Eszett) to SS
419        final char[] chrs = text.toUpperCase(Locale.GERMAN).toCharArray();
420
421        for (int index = 0; index < chrs.length; index++) {
422            switch (chrs[index]) {
423                case '\u00C4': // capital A, umlaut mark
424                    chrs[index] = 'A';
425                    break;
426                case '\u00DC': // capital U, umlaut mark
427                    chrs[index] = 'U';
428                    break;
429                case '\u00D6': // capital O, umlaut mark
430                    chrs[index] = 'O';
431                    break;
432                default:
433                    break;
434            }
435        }
436        return chrs;
437    }
438}