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 org.apache.commons.codec.EncoderException;
021import org.apache.commons.codec.StringEncoder;
022
023/**
024 * Encodes a string into a Metaphone value.
025 * <p>
026 * Initial Java implementation by <CITE>William B. Brogden. December, 1997</CITE>.
027 * Permission given by <CITE>wbrogden</CITE> for code to be used anywhere.
028 * <p>
029 * <CITE>Hanging on the Metaphone</CITE> by <CITE>Lawrence Philips</CITE> in <CITE>Computer Language of Dec. 1990,
030 * p 39.</CITE>
031 * <p>
032 * Note, that this does not match the algorithm that ships with PHP, or the algorithm found in the Perl implementations:
033 * </p>
034 * <ul>
035 * <li><a href="http://search.cpan.org/~mschwern/Text-Metaphone-1.96/Metaphone.pm">Text:Metaphone-1.96</a>
036 *  (broken link 4/30/2013) </li>
037 * <li><a href="https://metacpan.org/source/MSCHWERN/Text-Metaphone-1.96//Metaphone.pm">Text:Metaphone-1.96</a>
038 *  (link checked 4/30/2013) </li>
039 * </ul>
040 * <p>
041 * They have had undocumented changes from the originally published algorithm.
042 * For more information, see <a href="https://issues.apache.org/jira/browse/CODEC-57">CODEC-57</a>.
043 * <p>
044 * This class is conditionally thread-safe.
045 * The instance field {@link #maxCodeLen} is mutable {@link #setMaxCodeLen(int)}
046 * but is not volatile, and accesses are not synchronized.
047 * If an instance of the class is shared between threads, the caller needs to ensure that suitable synchronization
048 * is used to ensure safe publication of the value between threads, and must not invoke {@link #setMaxCodeLen(int)}
049 * after initial setup.
050 *
051 * @version $Id: Metaphone.html 891688 2013-12-24 20:49:46Z ggregory $
052 */
053public class Metaphone implements StringEncoder {
054
055    /**
056     * Five values in the English language
057     */
058    private static final String VOWELS = "AEIOU";
059
060    /**
061     * Variable used in Metaphone algorithm
062     */
063    private static final String FRONTV = "EIY";
064
065    /**
066     * Variable used in Metaphone algorithm
067     */
068    private static final String VARSON = "CSPTG";
069
070    /**
071     * The max code length for metaphone is 4
072     */
073    private int maxCodeLen = 4;
074
075    /**
076     * Creates an instance of the Metaphone encoder
077     */
078    public Metaphone() {
079        super();
080    }
081
082    /**
083     * Find the metaphone value of a String. This is similar to the
084     * soundex algorithm, but better at finding similar sounding words.
085     * All input is converted to upper case.
086     * Limitations: Input format is expected to be a single ASCII word
087     * with only characters in the A - Z range, no punctuation or numbers.
088     *
089     * @param txt String to find the metaphone code for
090     * @return A metaphone code corresponding to the String supplied
091     */
092    public String metaphone(final String txt) {
093        boolean hard = false;
094        if (txt == null || txt.length() == 0) {
095            return "";
096        }
097        // single character is itself
098        if (txt.length() == 1) {
099            return txt.toUpperCase(java.util.Locale.ENGLISH);
100        }
101
102        final char[] inwd = txt.toUpperCase(java.util.Locale.ENGLISH).toCharArray();
103
104        final StringBuilder local = new StringBuilder(40); // manipulate
105        final StringBuilder code = new StringBuilder(10); //   output
106        // handle initial 2 characters exceptions
107        switch(inwd[0]) {
108        case 'K':
109        case 'G':
110        case 'P': /* looking for KN, etc*/
111            if (inwd[1] == 'N') {
112                local.append(inwd, 1, inwd.length - 1);
113            } else {
114                local.append(inwd);
115            }
116            break;
117        case 'A': /* looking for AE */
118            if (inwd[1] == 'E') {
119                local.append(inwd, 1, inwd.length - 1);
120            } else {
121                local.append(inwd);
122            }
123            break;
124        case 'W': /* looking for WR or WH */
125            if (inwd[1] == 'R') {   // WR -> R
126                local.append(inwd, 1, inwd.length - 1);
127                break;
128            }
129            if (inwd[1] == 'H') {
130                local.append(inwd, 1, inwd.length - 1);
131                local.setCharAt(0, 'W'); // WH -> W
132            } else {
133                local.append(inwd);
134            }
135            break;
136        case 'X': /* initial X becomes S */
137            inwd[0] = 'S';
138            local.append(inwd);
139            break;
140        default:
141            local.append(inwd);
142        } // now local has working string with initials fixed
143
144        final int wdsz = local.length();
145        int n = 0;
146
147        while (code.length() < this.getMaxCodeLen() &&
148               n < wdsz ) { // max code size of 4 works well
149            final char symb = local.charAt(n);
150            // remove duplicate letters except C
151            if (symb != 'C' && isPreviousChar( local, n, symb ) ) {
152                n++;
153            } else { // not dup
154                switch(symb) {
155                case 'A':
156                case 'E':
157                case 'I':
158                case 'O':
159                case 'U':
160                    if (n == 0) {
161                        code.append(symb);
162                    }
163                    break; // only use vowel if leading char
164                case 'B':
165                    if ( isPreviousChar(local, n, 'M') &&
166                         isLastChar(wdsz, n) ) { // B is silent if word ends in MB
167                        break;
168                    }
169                    code.append(symb);
170                    break;
171                case 'C': // lots of C special cases
172                    /* discard if SCI, SCE or SCY */
173                    if ( isPreviousChar(local, n, 'S') &&
174                         !isLastChar(wdsz, n) &&
175                         FRONTV.indexOf(local.charAt(n + 1)) >= 0 ) {
176                        break;
177                    }
178                    if (regionMatch(local, n, "CIA")) { // "CIA" -> X
179                        code.append('X');
180                        break;
181                    }
182                    if (!isLastChar(wdsz, n) &&
183                        FRONTV.indexOf(local.charAt(n + 1)) >= 0) {
184                        code.append('S');
185                        break; // CI,CE,CY -> S
186                    }
187                    if (isPreviousChar(local, n, 'S') &&
188                        isNextChar(local, n, 'H') ) { // SCH->sk
189                        code.append('K');
190                        break;
191                    }
192                    if (isNextChar(local, n, 'H')) { // detect CH
193                        if (n == 0 &&
194                            wdsz >= 3 &&
195                            isVowel(local,2) ) { // CH consonant -> K consonant
196                            code.append('K');
197                        } else {
198                            code.append('X'); // CHvowel -> X
199                        }
200                    } else {
201                        code.append('K');
202                    }
203                    break;
204                case 'D':
205                    if (!isLastChar(wdsz, n + 1) &&
206                        isNextChar(local, n, 'G') &&
207                        FRONTV.indexOf(local.charAt(n + 2)) >= 0) { // DGE DGI DGY -> J
208                        code.append('J'); n += 2;
209                    } else {
210                        code.append('T');
211                    }
212                    break;
213                case 'G': // GH silent at end or before consonant
214                    if (isLastChar(wdsz, n + 1) &&
215                        isNextChar(local, n, 'H')) {
216                        break;
217                    }
218                    if (!isLastChar(wdsz, n + 1) &&
219                        isNextChar(local,n,'H') &&
220                        !isVowel(local,n+2)) {
221                        break;
222                    }
223                    if (n > 0 &&
224                        ( regionMatch(local, n, "GN") ||
225                          regionMatch(local, n, "GNED") ) ) {
226                        break; // silent G
227                    }
228                    if (isPreviousChar(local, n, 'G')) {
229                        // NOTE: Given that duplicated chars are removed, I don't see how this can ever be true
230                        hard = true;
231                    } else {
232                        hard = false;
233                    }
234                    if (!isLastChar(wdsz, n) &&
235                        FRONTV.indexOf(local.charAt(n + 1)) >= 0 &&
236                        !hard) {
237                        code.append('J');
238                    } else {
239                        code.append('K');
240                    }
241                    break;
242                case 'H':
243                    if (isLastChar(wdsz, n)) {
244                        break; // terminal H
245                    }
246                    if (n > 0 &&
247                        VARSON.indexOf(local.charAt(n - 1)) >= 0) {
248                        break;
249                    }
250                    if (isVowel(local,n+1)) {
251                        code.append('H'); // Hvowel
252                    }
253                    break;
254                case 'F':
255                case 'J':
256                case 'L':
257                case 'M':
258                case 'N':
259                case 'R':
260                    code.append(symb);
261                    break;
262                case 'K':
263                    if (n > 0) { // not initial
264                        if (!isPreviousChar(local, n, 'C')) {
265                            code.append(symb);
266                        }
267                    } else {
268                        code.append(symb); // initial K
269                    }
270                    break;
271                case 'P':
272                    if (isNextChar(local,n,'H')) {
273                        // PH -> F
274                        code.append('F');
275                    } else {
276                        code.append(symb);
277                    }
278                    break;
279                case 'Q':
280                    code.append('K');
281                    break;
282                case 'S':
283                    if (regionMatch(local,n,"SH") ||
284                        regionMatch(local,n,"SIO") ||
285                        regionMatch(local,n,"SIA")) {
286                        code.append('X');
287                    } else {
288                        code.append('S');
289                    }
290                    break;
291                case 'T':
292                    if (regionMatch(local,n,"TIA") ||
293                        regionMatch(local,n,"TIO")) {
294                        code.append('X');
295                        break;
296                    }
297                    if (regionMatch(local,n,"TCH")) {
298                        // Silent if in "TCH"
299                        break;
300                    }
301                    // substitute numeral 0 for TH (resembles theta after all)
302                    if (regionMatch(local,n,"TH")) {
303                        code.append('0');
304                    } else {
305                        code.append('T');
306                    }
307                    break;
308                case 'V':
309                    code.append('F'); break;
310                case 'W':
311                case 'Y': // silent if not followed by vowel
312                    if (!isLastChar(wdsz,n) &&
313                        isVowel(local,n+1)) {
314                        code.append(symb);
315                    }
316                    break;
317                case 'X':
318                    code.append('K');
319                    code.append('S');
320                    break;
321                case 'Z':
322                    code.append('S');
323                    break;
324                default:
325                    // do nothing
326                    break;
327                } // end switch
328                n++;
329            } // end else from symb != 'C'
330            if (code.length() > this.getMaxCodeLen()) {
331                code.setLength(this.getMaxCodeLen());
332            }
333        }
334        return code.toString();
335    }
336
337    private boolean isVowel(final StringBuilder string, final int index) {
338        return VOWELS.indexOf(string.charAt(index)) >= 0;
339    }
340
341    private boolean isPreviousChar(final StringBuilder string, final int index, final char c) {
342        boolean matches = false;
343        if( index > 0 &&
344            index < string.length() ) {
345            matches = string.charAt(index - 1) == c;
346        }
347        return matches;
348    }
349
350    private boolean isNextChar(final StringBuilder string, final int index, final char c) {
351        boolean matches = false;
352        if( index >= 0 &&
353            index < string.length() - 1 ) {
354            matches = string.charAt(index + 1) == c;
355        }
356        return matches;
357    }
358
359    private boolean regionMatch(final StringBuilder string, final int index, final String test) {
360        boolean matches = false;
361        if( index >= 0 &&
362            index + test.length() - 1 < string.length() ) {
363            final String substring = string.substring( index, index + test.length());
364            matches = substring.equals( test );
365        }
366        return matches;
367    }
368
369    private boolean isLastChar(final int wdsz, final int n) {
370        return n + 1 == wdsz;
371    }
372
373
374    /**
375     * Encodes an Object using the metaphone algorithm.  This method
376     * is provided in order to satisfy the requirements of the
377     * Encoder interface, and will throw an EncoderException if the
378     * supplied object is not of type java.lang.String.
379     *
380     * @param obj Object to encode
381     * @return An object (or type java.lang.String) containing the
382     *         metaphone code which corresponds to the String supplied.
383     * @throws EncoderException if the parameter supplied is not
384     *                          of type java.lang.String
385     */
386    @Override
387    public Object encode(final Object obj) throws EncoderException {
388        if (!(obj instanceof String)) {
389            throw new EncoderException("Parameter supplied to Metaphone encode is not of type java.lang.String");
390        }
391        return metaphone((String) obj);
392    }
393
394    /**
395     * Encodes a String using the Metaphone algorithm.
396     *
397     * @param str String object to encode
398     * @return The metaphone code corresponding to the String supplied
399     */
400    @Override
401    public String encode(final String str) {
402        return metaphone(str);
403    }
404
405    /**
406     * Tests is the metaphones of two strings are identical.
407     *
408     * @param str1 First of two strings to compare
409     * @param str2 Second of two strings to compare
410     * @return {@code true} if the metaphones of these strings are identical,
411     *        {@code false} otherwise.
412     */
413    public boolean isMetaphoneEqual(final String str1, final String str2) {
414        return metaphone(str1).equals(metaphone(str2));
415    }
416
417    /**
418     * Returns the maxCodeLen.
419     * @return int
420     */
421    public int getMaxCodeLen() { return this.maxCodeLen; }
422
423    /**
424     * Sets the maxCodeLen.
425     * @param maxCodeLen The maxCodeLen to set
426     */
427    public void setMaxCodeLen(final int maxCodeLen) { this.maxCodeLen = maxCodeLen; }
428
429}