    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    package org.apache.commons.codec.language;
    018
    019    import java.util.Locale;
    020
    021    import org.apache.commons.codec.EncoderException;
    022    import org.apache.commons.codec.StringEncoder;
    023
    024    /**
    025     * Match Rating Approach Phonetic Algorithm Developed by <CITE>Western Airlines</CITE> in 1977.
    026     *
    027     * This class is immutable and thread-safe.
    028     *
    029     * @see <a href="http://en.wikipedia.org/wiki/Match_rating_approach">Wikipedia - Match Rating Approach</a>
    030     * @since 1.8
    031     */
    032    public class MatchRatingApproachEncoder implements StringEncoder {
    033
    034        private static final String SPACE = " ";
    035
    036        private static final String EMPTY = "";
    037
    038        /**
    039         * Constants used mainly for the min rating value.
    040         */
    041        private static final int ONE = 1, TWO = 2, THREE = 3, FOUR = 4, FIVE = 5, SIX = 6, SEVEN = 7, EIGHT = 8,
    042                                 ELEVEN = 11, TWELVE = 12;
    043
    044        /**
    045         * The plain letter equivalent of the accented letters.
    046         */
    047        private static final String PLAIN_ASCII = "AaEeIiOoUu" + // grave
    048                "AaEeIiOoUuYy" + // acute
    049                "AaEeIiOoUuYy" + // circumflex
    050                "AaOoNn" + // tilde
    051                "AaEeIiOoUuYy" + // umlaut
    052                "Aa" + // ring
    053                "Cc" + // cedilla
    054                "OoUu"; // double acute
    055
    056        /**
    057         * Unicode characters corresponding to various accented letters. For example: \u00DA is U acute etc...
    058         */
    059        private static final String UNICODE = "\u00C0\u00E0\u00C8\u00E8\u00CC\u00EC\u00D2\u00F2\u00D9\u00F9" +
    060                "\u00C1\u00E1\u00C9\u00E9\u00CD\u00ED\u00D3\u00F3\u00DA\u00FA\u00DD\u00FD" +
    061                "\u00C2\u00E2\u00CA\u00EA\u00CE\u00EE\u00D4\u00F4\u00DB\u00FB\u0176\u0177" +
    062                "\u00C3\u00E3\u00D5\u00F5\u00D1\u00F1" +
    063                "\u00C4\u00E4\u00CB\u00EB\u00CF\u00EF\u00D6\u00F6\u00DC\u00FC\u0178\u00FF" +
    064                "\u00C5\u00E5" + "\u00C7\u00E7" + "\u0150\u0151\u0170\u0171";
    065
    066        private static final String[] DOUBLE_CONSONANT =
    067                new String[] { "BB", "CC", "DD", "FF", "GG", "HH", "JJ", "KK", "LL", "MM", "NN", "PP", "QQ", "RR", "SS",
    068                               "TT", "VV", "WW", "XX", "YY", "ZZ" };
    069
    070        /**
    071         * Cleans up a name: 1. Upper-cases everything 2. Removes some common punctuation 3. Removes accents 4. Removes any
    072         * spaces.
    073         *
    074         * <h2>API Usage</h2>
    075         * <p>
    076         * Consider this method private, it is package protected for unit testing only.
    077         * </p>
    078         *
    079         * @param name
    080         *            The name to be cleaned
    081         * @return The cleaned name
    082         */
    083        String cleanName(final String name) {
    084            String upperName = name.toUpperCase(Locale.ENGLISH);
    085
    086            final String[] charsToTrim = { "\\-", "[&]", "\\'", "\\.", "[\\,]" };
    087            for (final String str : charsToTrim) {
    088                upperName = upperName.replaceAll(str, EMPTY);
    089            }
    090
    091            upperName = removeAccents(upperName);
    092            upperName = upperName.replaceAll("\\s+", EMPTY);
    093
    094            return upperName;
    095        }
    096
    097        /**
    098         * Encodes an Object using the Match Rating Approach algo. Method is here to satisfy the requirements of the
    099         * Encoder interface Throws an EncoderException if input object is not of type java.lang.String.
    100         *
    101         * @param pObject
    102         *            Object to encode
    103         * @return An object (or type java.lang.String) containing the Match Rating Approach code which corresponds to the
    104         *         String supplied.
    105         * @throws EncoderException
    106         *             if the parameter supplied is not of type java.lang.String
    107         */
    108        @Override
    109        public final Object encode(final Object pObject) throws EncoderException {
    110            if (!(pObject instanceof String)) {
    111                throw new EncoderException(
    112                        "Parameter supplied to Match Rating Approach encoder is not of type java.lang.String");
    113            }
    114            return encode((String) pObject);
    115        }
    116
    117        /**
    118         * Encodes a String using the Match Rating Approach (MRA) algorithm.
    119         *
    120         * @param name
    121         *            String object to encode
    122         * @return The MRA code corresponding to the String supplied
    123         */
    124        @Override
    125        public final String encode(String name) {
    126            // Bulletproof for trivial input - NINO
    127            if (name == null || EMPTY.equalsIgnoreCase(name) || SPACE.equalsIgnoreCase(name) || name.length() == 1) {
    128                return EMPTY;
    129            }
    130
    131            // Preprocessing
    132            name = cleanName(name);
    133
    134            // BEGIN: Actual encoding part of the algorithm...
    135            // 1. Delete all vowels unless the vowel begins the word
    136            name = removeVowels(name);
    137
    138            // 2. Remove second consonant from any double consonant
    139            name = removeDoubleConsonants(name);
    140
    141            // 3. Reduce codex to 6 letters by joining the first 3 and last 3 letters
    142            name = getFirst3Last3(name);
    143
    144            return name;
    145        }
    146
    147        /**
    148         * Gets the first & last 3 letters of a name (if > 6 characters) Else just returns the name.
    149         *
    150         * <h2>API Usage</h2>
    151         * <p>
    152         * Consider this method private, it is package protected for unit testing only.
    153         * </p>
    154         *
    155         * @param name
    156         *            The string to get the substrings from
    157         * @return Annexed first & last 3 letters of input word.
    158         */
    159        String getFirst3Last3(final String name) {
    160            final int nameLength = name.length();
    161
    162            if (nameLength > SIX) {
    163                final String firstThree = name.substring(0, THREE);
    164                final String lastThree = name.substring(nameLength - THREE, nameLength);
    165                return firstThree + lastThree;
    166            } else {
    167                return name;
    168            }
    169        }
    170
    171        /**
    172         * Obtains the min rating of the length sum of the 2 names. In essence the larger the sum length the smaller the
    173         * min rating. Values strictly from documentation.
    174         *
    175         * <h2>API Usage</h2>
    176         * <p>
    177         * Consider this method private, it is package protected for unit testing only.
    178         * </p>
    179         *
    180         * @param sumLength
    181         *            The length of 2 strings sent down
    182         * @return The min rating value
    183         */
    184        int getMinRating(final int sumLength) {
    185            int minRating = 0;
    186
    187            if (sumLength <= FOUR) {
    188                minRating = FIVE;
    189            } else if (sumLength >= FIVE && sumLength <= SEVEN) {
    190                minRating = FOUR;
    191            } else if (sumLength >= EIGHT && sumLength <= ELEVEN) {
    192                minRating = THREE;
    193            } else if (sumLength == TWELVE) {
    194                minRating = TWO;
    195            } else {
    196                minRating = ONE; // docs said little here.
    197            }
    198
    199            return minRating;
    200        }
    201
    202        /**
    203         * Determines if two names are homophonous via Match Rating Approach (MRA) algorithm. It should be noted that the
    204         * strings are cleaned in the same way as {@link #encode(String)}.
    205         *
    206         * @param name1
    207         *            First of the 2 strings (names) to compare
    208         * @param name2
    209         *            Second of the 2 names to compare
    210         * @return <code>true</code> if the encodings are identical <code>false</code> otherwise.
    211         */
    212        public boolean isEncodeEquals(String name1, String name2) {
    213            // Bulletproof for trivial input - NINO
    214            if (name1 == null || EMPTY.equalsIgnoreCase(name1) || SPACE.equalsIgnoreCase(name1)) {
    215                return false;
    216            } else if (name2 == null || EMPTY.equalsIgnoreCase(name2) || SPACE.equalsIgnoreCase(name2)) {
    217                return false;
    218            } else if (name1.length() == 1 || name2.length() == 1) {
    219                return false;
    220            } else if (name1.equalsIgnoreCase(name2)) {
    221                return true;
    222            }
    223
    224            // Preprocessing
    225            name1 = cleanName(name1);
    226            name2 = cleanName(name2);
    227
    228            // Actual MRA Algorithm
    229
    230            // 1. Remove vowels
    231            name1 = removeVowels(name1);
    232            name2 = removeVowels(name2);
    233
    234            // 2. Remove double consonants
    235            name1 = removeDoubleConsonants(name1);
    236            name2 = removeDoubleConsonants(name2);
    237
    238            // 3. Reduce down to 3 letters
    239            name1 = getFirst3Last3(name1);
    240            name2 = getFirst3Last3(name2);
    241
    242            // 4. Check for length difference - if 3 or greater then no similarity
    243            // comparison is done
    244            if (Math.abs(name1.length() - name2.length()) >= THREE) {
    245                return false;
    246            }
    247
    248            // 5. Obtain the minimum rating value by calculating the length sum of the
    249            // encoded Strings and sending it down.
    250            final int sumLength = Math.abs(name1.length() + name2.length());
    251            int minRating = 0;
    252            minRating = getMinRating(sumLength);
    253
    254            // 6. Process the encoded Strings from left to right and remove any
    255            // identical characters found from both Strings respectively.
    256            final int count = leftToRightThenRightToLeftProcessing(name1, name2);
    257
    258            // 7. Each PNI item that has a similarity rating equal to or greater than
    259            // the min is considered to be a good candidate match
    260            return count >= minRating;
    261
    262        }
    263
    264        /**
    265         * Determines if a letter is a vowel.
    266         *
    267         * <h2>API Usage</h2>
    268         * <p>
    269         * Consider this method private, it is package protected for unit testing only.
    270         * </p>
    271         *
    272         * @param letter
    273         *            The letter under investiagtion
    274         * @return True if a vowel, else false
    275         */
    276        boolean isVowel(final String letter) {
    277            return letter.equalsIgnoreCase("E") || letter.equalsIgnoreCase("A") || letter.equalsIgnoreCase("O") ||
    278                   letter.equalsIgnoreCase("I") || letter.equalsIgnoreCase("U");
    279        }
    280
    281        /**
    282         * Processes the names from left to right (first) then right to left removing identical letters in same positions.
    283         * Then subtracts the longer string that remains from 6 and returns this.
    284         *
    285         * <h2>API Usage</h2>
    286         * <p>
    287         * Consider this method private, it is package protected for unit testing only.
    288         * </p>
    289         *
    290         * @param name1
    291         *            name2
    292         * @return
    293         */
    294        int leftToRightThenRightToLeftProcessing(final String name1, final String name2) {
    295            final char[] name1Char = name1.toCharArray();
    296            final char[] name2Char = name2.toCharArray();
    297
    298            final int name1Size = name1.length() - 1;
    299            final int name2Size = name2.length() - 1;
    300
    301            String name1LtRStart = EMPTY;
    302            String name1LtREnd = EMPTY;
    303
    304            String name2RtLStart = EMPTY;
    305            String name2RtLEnd = EMPTY;
    306
    307            for (int i = 0; i < name1Char.length; i++) {
    308                if (i > name2Size) {
    309                    break;
    310                }
    311
    312                name1LtRStart = name1.substring(i, i + 1);
    313                name1LtREnd = name1.substring(name1Size - i, name1Size - i + 1);
    314
    315                name2RtLStart = name2.substring(i, i + 1);
    316                name2RtLEnd = name2.substring(name2Size - i, name2Size - i + 1);
    317
    318                // Left to right...
    319                if (name1LtRStart.equals(name2RtLStart)) {
    320                    name1Char[i] = ' ';
    321                    name2Char[i] = ' ';
    322                }
    323
    324                // Right to left...
    325                if (name1LtREnd.equals(name2RtLEnd)) {
    326                    name1Char[name1Size - i] = ' ';
    327                    name2Char[name2Size - i] = ' ';
    328                }
    329            }
    330
    331            // Char arrays -> string & remove extraneous space
    332            final String strA = new String(name1Char).replaceAll("\\s+", EMPTY);
    333            final String strB = new String(name2Char).replaceAll("\\s+", EMPTY);
    334
    335            // Final bit - subtract longest string from 6 and return this int value
    336            if (strA.length() > strB.length()) {
    337                return Math.abs(SIX - strA.length());
    338            } else {
    339                return Math.abs(SIX - strB.length());
    340            }
    341        }
    342
    343        /**
    344         * Removes accented letters and replaces with non-accented ascii equivalent Case is preserved.
    345         * http://www.codecodex.com/wiki/Remove_accent_from_letters_%28ex_.%C3%A9_to_e%29
    346         *
    347         * @param accentedWord
    348         *            The word that may have accents in it.
    349         * @return De-accented word
    350         */
    351        String removeAccents(final String accentedWord) {
    352            if (accentedWord == null) {
    353                return null;
    354            }
    355
    356            final StringBuilder sb = new StringBuilder();
    357            final int n = accentedWord.length();
    358
    359            for (int i = 0; i < n; i++) {
    360                final char c = accentedWord.charAt(i);
    361                final int pos = UNICODE.indexOf(c);
    362                if (pos > -1) {
    363                    sb.append(PLAIN_ASCII.charAt(pos));
    364                } else {
    365                    sb.append(c);
    366                }
    367            }
    368
    369            return sb.toString();
    370        }
    371
    372        /**
    373         * Replaces any double consonant pair with the single letter equivalent.
    374         *
    375         * <h2>API Usage</h2>
    376         * <p>
    377         * Consider this method private, it is package protected for unit testing only.
    378         * </p>
    379         *
    380         * @param name
    381         *            String to have double consonants removed
    382         * @return Single consonant word
    383         */
    384        String removeDoubleConsonants(final String name) {
    385            String replacedName = name.toUpperCase();
    386            for (final String dc : DOUBLE_CONSONANT) {
    387                if (replacedName.contains(dc)) {
    388                    final String singleLetter = dc.substring(0, 1);
    389                    replacedName = replacedName.replace(dc, singleLetter);
    390                }
    391            }
    392            return replacedName;
    393        }
    394
    395        /**
    396         * Deletes all vowels unless the vowel begins the word.
    397         *
    398         * <h2>API Usage</h2>
    399         * <p>
    400         * Consider this method private, it is package protected for unit testing only.
    401         * </p>
    402         *
    403         * @param name
    404         *            The name to have vowels removed
    405         * @return De-voweled word
    406         */
    407        String removeVowels(String name) {
    408            // Extract first letter
    409            final String firstLetter = name.substring(0, 1);
    410
    411            name = name.replaceAll("A", EMPTY);
    412            name = name.replaceAll("E", EMPTY);
    413            name = name.replaceAll("I", EMPTY);
    414            name = name.replaceAll("O", EMPTY);
    415            name = name.replaceAll("U", EMPTY);
    416
    417            name = name.replaceAll("\\s{2,}\\b", SPACE);
    418
    419            // return isVowel(firstLetter) ? (firstLetter + name) : name;
    420            if (isVowel(firstLetter)) {
    421                return firstLetter + name;
    422            } else {
    423                return name;
    424            }
    425        }
    426    }