Nysiis.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      https://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */

  17. package org.apache.commons.codec.language;

  18. import java.util.regex.Pattern;

  19. import org.apache.commons.codec.EncoderException;
  20. import org.apache.commons.codec.StringEncoder;

  21. /**
  22.  * Encodes a string into a NYSIIS value. NYSIIS is an encoding used to relate similar names, but can also be used as a
  23.  * general purpose scheme to find word with similar phonemes.
  24.  * <p>
  25.  * NYSIIS features an accuracy increase of 2.7% over the traditional Soundex algorithm.
  26.  * </p>
  27.  * <p>
  28.  * Algorithm description:
  29.  * </p>
  30.  * <pre>
  31.  * 1. Transcode first characters of name
  32.  *   1a. MAC -&gt;   MCC
  33.  *   1b. KN  -&gt;   NN
  34.  *   1c. K   -&gt;   C
  35.  *   1d. PH  -&gt;   FF
  36.  *   1e. PF  -&gt;   FF
  37.  *   1f. SCH -&gt;   SSS
  38.  * 2. Transcode last characters of name
  39.  *   2a. EE, IE          -&gt;   Y
  40.  *   2b. DT,RT,RD,NT,ND  -&gt;   D
  41.  * 3. First character of key = first character of name
  42.  * 4. Transcode remaining characters by following these rules, incrementing by one character each time
  43.  *   4a. EV  -&gt;   AF  else A,E,I,O,U -&gt; A
  44.  *   4b. Q   -&gt;   G
  45.  *   4c. Z   -&gt;   S
  46.  *   4d. M   -&gt;   N
  47.  *   4e. KN  -&gt;   N   else K -&gt; C
  48.  *   4f. SCH -&gt;   SSS
  49.  *   4g. PH  -&gt;   FF
  50.  *   4h. H   -&gt;   If previous or next is non-vowel, previous
  51.  *   4i. W   -&gt;   If previous is vowel, previous
  52.  *   4j. Add current to key if current != last key character
  53.  * 5. If last character is S, remove it
  54.  * 6. If last characters are AY, replace with Y
  55.  * 7. If last character is A, remove it
  56.  * 8. Collapse all strings of repeated characters
  57.  * 9. Add original first character of name as first character of key
  58.  * </pre>
  59.  * <p>
  60.  * This class is immutable and thread-safe.
  61.  * </p>
  62.  *
  63.  * @see <a href="https://en.wikipedia.org/wiki/NYSIIS">NYSIIS on Wikipedia</a>
  64.  * @see <a href="http://www.dropby.com/NYSIIS.html">NYSIIS on dropby.com</a>
  65.  * @see Soundex
  66.  * @since 1.7
  67.  */
  68. public class Nysiis implements StringEncoder {

  69.     private static final char[] CHARS_A   = { 'A' };
  70.     private static final char[] CHARS_AF  = { 'A', 'F' };
  71.     private static final char[] CHARS_C   = { 'C' };
  72.     private static final char[] CHARS_FF  = { 'F', 'F' };
  73.     private static final char[] CHARS_G   = { 'G' };
  74.     private static final char[] CHARS_N   = { 'N' };
  75.     private static final char[] CHARS_NN  = { 'N', 'N' };
  76.     private static final char[] CHARS_S   = { 'S' };
  77.     private static final char[] CHARS_SSS = { 'S', 'S', 'S' };

  78.     private static final Pattern PAT_MAC    = Pattern.compile("^MAC");
  79.     private static final Pattern PAT_KN     = Pattern.compile("^KN");
  80.     private static final Pattern PAT_K      = Pattern.compile("^K");
  81.     private static final Pattern PAT_PH_PF  = Pattern.compile("^(PH|PF)");
  82.     private static final Pattern PAT_SCH    = Pattern.compile("^SCH");
  83.     private static final Pattern PAT_EE_IE  = Pattern.compile("(EE|IE)$");
  84.     private static final Pattern PAT_DT_ETC = Pattern.compile("(DT|RT|RD|NT|ND)$");

  85.     private static final char SPACE = ' ';
  86.     private static final int TRUE_LENGTH = 6;

  87.     /**
  88.      * Tests if the given character is a vowel.
  89.      *
  90.      * @param c
  91.      *            the character to test.
  92.      * @return {@code true} if the character is a vowel, {@code false} otherwise.
  93.      */
  94.     private static boolean isVowel(final char c) {
  95.         return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
  96.     }

  97.     /**
  98.      * Transcodes the remaining parts of the String. The method operates on a sliding window, looking at 4 characters at
  99.      * a time: [i-1, i, i+1, i+2].
  100.      *
  101.      * @param prev
  102.      *            the previous character.
  103.      * @param curr
  104.      *            the current character.
  105.      * @param next
  106.      *            the next character.
  107.      * @param aNext
  108.      *            the after next character.
  109.      * @return a transcoded array of characters, starting from the current position.
  110.      */
  111.     private static char[] transcodeRemaining(final char prev, final char curr, final char next, final char aNext) {
  112.         // 1. EV -> AF
  113.         if (curr == 'E' && next == 'V') {
  114.             return CHARS_AF;
  115.         }

  116.         // A, E, I, O, U -> A
  117.         if (isVowel(curr)) {
  118.             return CHARS_A;
  119.         }

  120.         // 2. Q -> G, Z -> S, M -> N

  121.         // 3. KN -> NN else K -> C
  122.         switch (curr) {
  123.         case 'Q':
  124.             return CHARS_G;
  125.         case 'Z':
  126.             return CHARS_S;
  127.         case 'M':
  128.             return CHARS_N;
  129.         case 'K':
  130.             if (next == 'N') {
  131.                 return CHARS_NN;
  132.             }
  133.             return CHARS_C;
  134.         default:
  135.             break;
  136.         }

  137.         // 4. SCH -> SSS
  138.         if (curr == 'S' && next == 'C' && aNext == 'H') {
  139.             return CHARS_SSS;
  140.         }

  141.         // PH -> FF
  142.         if (curr == 'P' && next == 'H') {
  143.             return CHARS_FF;
  144.         }

  145.         // 5. H -> If previous or next is a non vowel, previous.
  146.         if (curr == 'H' && (!isVowel(prev) || !isVowel(next))) {
  147.             return new char[] { prev };
  148.         }

  149.         // 6. W -> If previous is vowel, previous.
  150.         if (curr == 'W' && isVowel(prev)) {
  151.             return new char[] { prev };
  152.         }

  153.         return new char[] { curr };
  154.     }

  155.     /** Indicates the strict mode. */
  156.     private final boolean strict;

  157.     /**
  158.      * Creates an instance of the {@link Nysiis} encoder with strict mode (original form),
  159.      * i.e. encoded strings have a maximum length of 6.
  160.      */
  161.     public Nysiis() {
  162.         this(true);
  163.     }

  164.     /**
  165.      * Create an instance of the {@link Nysiis} encoder with the specified strict mode:
  166.      *
  167.      * <ul>
  168.      *  <li>{@code true}: encoded strings have a maximum length of 6</li>
  169.      *  <li>{@code false}: encoded strings may have arbitrary length</li>
  170.      * </ul>
  171.      *
  172.      * @param strict
  173.      *            the strict mode.
  174.      */
  175.     public Nysiis(final boolean strict) {
  176.         this.strict = strict;
  177.     }

  178.     /**
  179.      * Encodes an Object using the NYSIIS algorithm. This method is provided in order to satisfy the requirements of the Encoder interface, and will throw an
  180.      * {@link EncoderException} if the supplied object is not of type {@link String}.
  181.      *
  182.      * @param obj Object to encode.
  183.      * @return An object (or a {@link String}) containing the NYSIIS code which corresponds to the given String.
  184.      * @throws EncoderException         if the parameter supplied is not of a {@link String}.
  185.      * @throws IllegalArgumentException if a character is not mapped.
  186.      */
  187.     @Override
  188.     public Object encode(final Object obj) throws EncoderException {
  189.         if (!(obj instanceof String)) {
  190.             throw new EncoderException("Parameter supplied to Nysiis encode is not of type java.lang.String");
  191.         }
  192.         return nysiis((String) obj);
  193.     }

  194.     /**
  195.      * Encodes a String using the NYSIIS algorithm.
  196.      *
  197.      * @param str A String object to encode.
  198.      * @return A Nysiis code corresponding to the String supplied.
  199.      * @throws IllegalArgumentException if a character is not mapped.
  200.      */
  201.     @Override
  202.     public String encode(final String str) {
  203.         return nysiis(str);
  204.     }

  205.     /**
  206.      * Indicates the strict mode for this {@link Nysiis} encoder.
  207.      *
  208.      * @return {@code true} if the encoder is configured for strict mode, {@code false} otherwise
  209.      */
  210.     public boolean isStrict() {
  211.         return this.strict;
  212.     }

  213.     /**
  214.      * Retrieves the NYSIIS code for a given String object.
  215.      *
  216.      * @param str String to encode using the NYSIIS algorithm.
  217.      * @return A NYSIIS code for the String supplied.
  218.      */
  219.     public String nysiis(String str) {
  220.         if (str == null) {
  221.             return null;
  222.         }

  223.         // Use the same clean rules as Soundex
  224.         str = SoundexUtils.clean(str);

  225.         if (str.isEmpty()) {
  226.             return str;
  227.         }

  228.         // Translate first characters of name:
  229.         // MAC -> MCC, KN -> NN, K -> C, PH | PF -> FF, SCH -> SSS
  230.         str = PAT_MAC.matcher(str).replaceFirst("MCC");
  231.         str = PAT_KN.matcher(str).replaceFirst("NN");
  232.         str = PAT_K.matcher(str).replaceFirst("C");
  233.         str = PAT_PH_PF.matcher(str).replaceFirst("FF");
  234.         str = PAT_SCH.matcher(str).replaceFirst("SSS");

  235.         // Translate last characters of name:
  236.         // EE -> Y, IE -> Y, DT | RT | RD | NT | ND -> D
  237.         str = PAT_EE_IE.matcher(str).replaceFirst("Y");
  238.         str = PAT_DT_ETC.matcher(str).replaceFirst("D");

  239.         // First character of key = first character of name.
  240.         final StringBuilder key = new StringBuilder(str.length());
  241.         key.append(str.charAt(0));

  242.         // Transcode remaining characters, incrementing by one character each time
  243.         final char[] chars = str.toCharArray();
  244.         final int len = chars.length;

  245.         for (int i = 1; i < len; i++) {
  246.             final char next = i < len - 1 ? chars[i + 1] : SPACE;
  247.             final char aNext = i < len - 2 ? chars[i + 2] : SPACE;
  248.             final char[] transcoded = transcodeRemaining(chars[i - 1], chars[i], next, aNext);
  249.             System.arraycopy(transcoded, 0, chars, i, transcoded.length);

  250.             // only append the current char to the key if it is different from the last one
  251.             if (chars[i] != chars[i - 1]) {
  252.                 key.append(chars[i]);
  253.             }
  254.         }

  255.         if (key.length() > 1) {
  256.             char lastChar = key.charAt(key.length() - 1);

  257.             // If last character is S, remove it.
  258.             if (lastChar == 'S') {
  259.                 key.deleteCharAt(key.length() - 1);
  260.                 lastChar = key.charAt(key.length() - 1);
  261.             }

  262.             if (key.length() > 2) {
  263.                 final char last2Char = key.charAt(key.length() - 2);
  264.                 // If last characters are AY, replace with Y.
  265.                 if (last2Char == 'A' && lastChar == 'Y') {
  266.                     key.deleteCharAt(key.length() - 2);
  267.                 }
  268.             }

  269.             // If last character is A, remove it.
  270.             if (lastChar == 'A') {
  271.                 key.deleteCharAt(key.length() - 1);
  272.             }
  273.         }

  274.         final String string = key.toString();
  275.         return isStrict() ? string.substring(0, Math.min(TRUE_LENGTH, string.length())) : string;
  276.     }

  277. }