    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}