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