    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}&uuml;{@code ller-L}&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"}</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"}</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         * Stores 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         * @param code the code to store.
    246         */
    247        public void put(final char code) {
    248            if (code != CHAR_IGNORE && lastCode != code && (code != '0' || length == 0)) {
    249                data[length] = code;
    250                length++;
    251            }
    252            lastCode = code;
    253        }
    254
    255        @Override
    256        protected char[] copyData(final int start, final int length) {
    257            final char[] newData = new char[length];
    258            System.arraycopy(data, start, newData, 0, length);
    259            return newData;
    260        }
    261    }
    262
    263    private class CologneInputBuffer extends CologneBuffer {
    264
    265        public CologneInputBuffer(final char[] data) {
    266            super(data);
    267        }
    268
    269        @Override
    270        protected char[] copyData(final int start, final int length) {
    271            final char[] newData = new char[length];
    272            System.arraycopy(data, data.length - this.length + start, newData, 0, length);
    273            return newData;
    274        }
    275
    276        public char getNextChar() {
    277            return data[getNextPos()];
    278        }
    279
    280        protected int getNextPos() {
    281            return data.length - length;
    282        }
    283
    284        public char removeNext() {
    285            final char ch = getNextChar();
    286            length--;
    287            return ch;
    288        }
    289    }
    290
    291    /*
    292     * Returns whether the array contains the key, or not.
    293     */
    294    private static boolean arrayContains(final char[] arr, final char key) {
    295        for (final char element : arr) {
    296            if (element == key) {
    297                return true;
    298            }
    299        }
    300        return false;
    301    }
    302
    303    /**
    304     * <p>
    305     * Implements the <i>K&ouml;lner Phonetik</i> algorithm.
    306     * </p>
    307     * <p>
    308     * In contrast to the initial description of the algorithm, this implementation does the encoding in one pass.
    309     * </p>
    310     *
    311     * @param text The source text to encode
    312     * @return the corresponding encoding according to the <i>K&ouml;lner Phonetik</i> algorithm
    313     */
    314    public String colognePhonetic(final String text) {
    315        if (text == null) {
    316            return null;
    317        }
    318
    319        final CologneInputBuffer input = new CologneInputBuffer(preprocess(text));
    320        final CologneOutputBuffer output = new CologneOutputBuffer(input.length() * 2);
    321
    322        char nextChar;
    323
    324        char lastChar = CHAR_IGNORE;
    325        char chr;
    326
    327        while (input.length() > 0) {
    328            chr = input.removeNext();
    329
    330            if (input.length() > 0) {
    331                nextChar = input.getNextChar();
    332            } else {
    333                nextChar = CHAR_IGNORE;
    334            }
    335
    336            if (chr < 'A' || chr > 'Z') {
    337                    continue; // ignore unwanted characters
    338            }
    339
    340            if (arrayContains(AEIJOUY, chr)) {
    341                output.put('0');
    342            } else if (chr == 'B' || (chr == 'P' && nextChar != 'H')) {
    343                output.put('1');
    344            } else if ((chr == 'D' || chr == 'T') && !arrayContains(CSZ, nextChar)) {
    345                output.put('2');
    346            } else if (arrayContains(FPVW, chr)) {
    347                output.put('3');
    348            } else if (arrayContains(GKQ, chr)) {
    349                output.put('4');
    350            } else if (chr == 'X' && !arrayContains(CKQ, lastChar)) {
    351                output.put('4');
    352                output.put('8');
    353            } else if (chr == 'S' || chr == 'Z') {
    354                output.put('8');
    355            } else if (chr == 'C') {
    356                if (output.length() == 0) {
    357                    if (arrayContains(AHKLOQRUX, nextChar)) {
    358                        output.put('4');
    359                    } else {
    360                        output.put('8');
    361                    }
    362                } else {
    363                    if (arrayContains(SZ, lastChar) || !arrayContains(AHKOQUX, nextChar)) {
    364                        output.put('8');
    365                    } else {
    366                        output.put('4');
    367                    }
    368                }
    369            } else if (arrayContains(DTX, chr)) {
    370                output.put('8');
    371            } else if (chr == 'R') {
    372                output.put('7');
    373            } else if (chr == 'L') {
    374                output.put('5');
    375            } else if (chr == 'M' || chr == 'N') {
    376                output.put('6');
    377            } else if (chr == 'H') {
    378                output.put(CHAR_IGNORE); // needed by put
    379            } else {
    380                // ignored; should not happen
    381            }
    382
    383            lastChar = chr;
    384        }
    385        return output.toString();
    386    }
    387
    388    @Override
    389    public Object encode(final Object object) throws EncoderException {
    390        if (!(object instanceof String)) {
    391            throw new EncoderException("This method's parameter was expected to be of the type " +
    392                String.class.getName() +
    393                ". But actually it was of the type " +
    394                object.getClass().getName() +
    395                ".");
    396        }
    397        return encode((String) object);
    398    }
    399
    400    @Override
    401    public String encode(final String text) {
    402        return colognePhonetic(text);
    403    }
    404
    405    /**
    406     * Compares the first encoded string to the second encoded string.
    407     *
    408     * @param text1 source text to encode before testing for equality.
    409     * @param text2 source text to encode before testing for equality.
    410     * @return {@code true} if the encoding the first string equals the encoding of the second string, {@code false}
    411     *         otherwise
    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     * The following characters are mapped:
    420     * <ul>
    421     * <li>capital A, umlaut mark</li>
    422     * <li>capital U, umlaut mark</li>
    423     * <li>capital O, umlaut mark</li>
    424     * <li>small sharp s, German</li>
    425     * </ul>
    426     */
    427    private char[] preprocess(final String text) {
    428        // This converts German small sharp s (Eszett) to SS
    429        final char[] chrs = text.toUpperCase(Locale.GERMAN).toCharArray();
    430
    431        for (int index = 0; index < chrs.length; index++) {
    432            switch (chrs[index]) {
    433                case '\u00C4': // capital A, umlaut mark
    434                    chrs[index] = 'A';
    435                    break;
    436                case '\u00DC': // capital U, umlaut mark
    437                    chrs[index] = 'U';
    438                    break;
    439                case '\u00D6': // capital O, umlaut mark
    440                    chrs[index] = 'O';
    441                    break;
    442                default:
    443                    break;
    444            }
    445        }
    446        return chrs;
    447    }
    448}