ń ǹ ň ñ ṅ ņ ṇ ṋ ṉ ̈ ɲ ƞ ᶇ ɳ ȵ --> n or Remove diacritical marks from unicode chars

Question

I am looking an algorithm that can map between characters with diacritics (tilde, circumflex, caret, umlaut, caron) and their "simple" character.

For example:

ń  ǹ  ň  ñ  ṅ  ņ  ṇ  ṋ  ṉ  ̈  ɲ  ƞ ᶇ ɳ ȵ  --> n
á --> a
ä --> a
ấ --> a
ṏ --> o

etc

UPDATE

1) I want to do this in Java, although I suspect it should be something unicode-y and should be doable reasonably easily in any language.

2) Purpose: to allow easily search for words with diacritical marks. For example, if I have a database of tennis players, and Björn_Borg is entered, I will also keep Bjorn_Borg so I can find it if someone enters Bjorn and not Björn.

Answer 1

Unicode has specific diatric characters (which are composite characters) and a string can be converted so that the character and the diatrics are separated. Then, you can just remove the diatricts from the string and you're basically done.

For more information on normalization, decompositions and equivalence, see The Unicode Standard at the Unicode home page.

However, how you can actually achieve this depends on the framework/OS/... you're working on. If you're using .NET, you can use the String.Normalize method accepting the System.Text.NormalizationForm enumeration.

Answer 2

There is a draft report on character folding on the unicode website which has a lot of relevant material. See specifically Section 4.1. "Folding algorithm".

Here's a discussion and implementation of diacritic marker removal using Perl.

These existing SO questions are related:

• How to convert UTF-8 to US ASCII
• How to change diacritic characters to non-diacritic ones

Answer 3

you could use the Normalizer from java.text

System.out.println(new String(Normalizer.normalize("ń ǹ ň ñ ṅ ņ ṇ ṋ", Normalizer.Form.NFKD).getBytes("ascii"), "ascii"));

but there is still some work to do, since java makes strange things with unconvertable unichars (does not ignore them, does not throw an exception). But I think you could use that as an starting point.

Answer 4

The easiest way (to me) would be to simply maintain a sparse mapping array which simply changes your Unicode code points into displayable strings.

Such as:

start    = 0x00C0
size     = 23
mappings = {
    "A","A","A","A","A","A","AE","C",
    "E","E","E","E","I","I","I", "I",
    "D","N","O","O","O","O","O"
}
start    = 0x00D8
size     = 6
mappings = {
    "O","U","U","U","U","Y"
}
start    = 0x00E0
size     = 23
mappings = {
    "a","a","a","a","a","a","ae","c",
    "e","e","e","e","i","i","i", "i",
    "d","n","o","o","o","o","o"
}
start    = 0x00F8
size     = 6
mappings = {
    "o","u","u","u","u","y"
}
: : :

The use of a sparse array will allow you to efficiently represent replacements even when they in widely spaced sections of the Unicode table. String replacements will allow arbitrary sequences to replace your diacritics (such as the æ grapheme becoming ae).

This is a language-agnostic answer so, if you have a specific language in mind, there will be better ways (although they'll all likely come down to this at the lowest levels anyway).

Answer 5

i have done this recently in java:

public static final Pattern DIACRITICS_AND_FRIENDS 
 = Pattern.compile("[\\p{InCombiningDiacriticalMarks}\\p{IsLm}\\p{IsSk}]+");


private static String stripDiacritics(String str) {
 str = Normalizer.normalize(str, Normalizer.Form.NFD);
 str = DIACRITICS_AND_FRIENDS.matcher(str).replaceAll("");
 return str;
}

this will do as you specified: stripDiacritics(Björn) = Bjorn

but it will fail on f. ex Białystok, because the ł character is not diacritic.

if you want to have a full-blown string simplifier you will need a second cleanup round, for some more special characters that are not diacritics. is this map i have included the most common special characters that appear in our customer names. it is not a complete list, but it will give you the idea how to do extend it. the immutableMap is just a simple class from google-collections.

public class StringSimplifier {

 public static final char DEFAULT_REPLACE_CHAR = '-';
 public static final String DEFAULT_REPLACE = String.valueOf(DEFAULT_REPLACE_CHAR);
 private static final ImmutableMap<String, String> NONDIACRITICS = ImmutableMap.<String, String>builder()
  //remove crap strings with no sematics
  .put(".", "")
  .put("\"", "")
  .put("'", "")
   //keep relevant characters as seperation
  .put(" ", DEFAULT_REPLACE)
  .put("]", DEFAULT_REPLACE)
  .put("[", DEFAULT_REPLACE)
  .put(")", DEFAULT_REPLACE)
  .put("(", DEFAULT_REPLACE)
  .put("=", DEFAULT_REPLACE)
  .put("!", DEFAULT_REPLACE)
  .put("/", DEFAULT_REPLACE)
  .put("\\", DEFAULT_REPLACE)
  .put("&", DEFAULT_REPLACE)
  .put(",", DEFAULT_REPLACE)
  .put("?", DEFAULT_REPLACE)
  .put("°", DEFAULT_REPLACE) //remove ?? is diacritic?
  .put("|", DEFAULT_REPLACE)
  .put("<", DEFAULT_REPLACE)
  .put(">", DEFAULT_REPLACE)
  .put(";", DEFAULT_REPLACE)
  .put(":", DEFAULT_REPLACE)
  .put("_", DEFAULT_REPLACE)
  .put("#", DEFAULT_REPLACE)
  .put("~", DEFAULT_REPLACE)
  .put("+", DEFAULT_REPLACE)
  .put("*", DEFAULT_REPLACE)
   //replace non-diacritics as their equivalent chars
  .put("\u0141", "l") // BiaLystock
  .put("\u0142", "l") // Bialystock
  .put("ß", "ss")
  .put("æ", "ae")
  .put("ø", "o")
  .put("©", "c")
  .put("\u00D0", "d") // all Ð ð from http://de.wikipedia.org/wiki/%C3%90
  .put("\u00F0", "d")
  .put("\u0110", "d")
  .put("\u0111", "d")
  .put("\u0189", "d")
  .put("\u0256", "d")
  .put("\u00DE", "th") // thorn Þ 
  .put("\u00FE", "th") // thorn þ
  .build();


 public static String simplifiedString(String orig) {
  String str = orig;
  if (str == null) {
   return null;
  }
  str = stripDiacritics(str);
  str = stripNonDiacritics(str);
  if (str.length() == 0) {
   // ugly special case to work around non-existing empty strings in oracle. store original crapstring as simplified..
   //  would return empty string if oracle could store it.
   return orig;
  }
  return str.toLowerCase();
 }

 private static String stripNonDiacritics(String orig) {
  StringBuffer ret = new StringBuffer();
  String lastchar = null;
  for (int i = 0; i < orig.length(); i++) {
   String source = orig.substring(i, i + 1);
   String replace = NONDIACRITICS.get(source);
   String toReplace = replace == null ? String.valueOf(source) : replace;
   if (DEFAULT_REPLACE.equals(lastchar) && DEFAULT_REPLACE.equals(toReplace)) {
    toReplace = "";
   } else {
    lastchar = toReplace;
   }
   ret.append(toReplace);
  }
  if (ret.length() > 0 && DEFAULT_REPLACE_CHAR == ret.charAt(ret.length() - 1)) {
   ret.deleteCharAt(ret.length() - 1);
  }
  return ret.toString();
 }

 /*
 special regexp char ranges relevant for simplification -> see http://docstore.mik.ua/orelly/perl/prog3/ch05_04.htm 
 InCombiningDiacriticalMarks: special marks that are part of "normal" ä, ö, î etc..
  IsSk: Symbol, Modifier see http://www.fileformat.info/info/unicode/category/Sk/list.htm
  IsLm: Letter, Modifier see http://www.fileformat.info/info/unicode/category/Lm/list.htm
  */
 public static final Pattern DIACRITICS_AND_FRIENDS 
  = Pattern.compile("[\\p{InCombiningDiacriticalMarks}\\p{IsLm}\\p{IsSk}]+");


 private static String stripDiacritics(String str) {
  str = Normalizer.normalize(str, Normalizer.Form.NFD);
  str = DIACRITICS_AND_FRIENDS.matcher(str).replaceAll("");
  return str;
 }
}

Answer 6

The core java.text package was designed to address this use case (matching strings without caring about diacritics, case, etc.).

Configure a Collator to sort on PRIMARY differences in characters. With that, create a CollationKey for each string. If all of your code is in Java, you can use the CollationKey directly. If you need to store the keys in a database or other sort of index, you can convert it to a byte array.

These classes use the Unicode standard case folding data to determine which characters are equivalent, and support various decomposition strategies.

Collator c = Collator.getInstance();
c.setStrength(Collator.PRIMARY);
Map<CollationKey, String> dictionary = new TreeMap<CollationKey, String>();
dictionary.put(c.getCollationKey("Björn"), "Björn");
...
CollationKey query = c.getCollationKey("bjorn");
System.out.println(dictionary.get(query)); // --> "Björn"

Note that collators are locale-specific. This is because "alphabetical order" is differs between locales (and even over time, as has been the case with Spanish). The Collator class relieves you from having to track all of these rules and keep them up to date.

Answer 7

In Windows and .NET I just convert string encoding, that way I avoid manual mapping and coding. Try to play with string encoding.

Answer 8

Something to consider: if you go the route of trying to get a single "translation" of each word, you may miss out on some possible alternates.

For instance, in German, when replacing the "s-set", some people might use "B", while others might use "ss". Or, replacing an umlauted o with "o" or "oe". Any solution you come up with, ideally, I would think should include both.

Answer 9

For future reference, here is a C# extension method that removes accents.

public static class StringExtensions
{
    public static string RemoveDiacritics(this string str)
    {
        return new string(
            str.Normalize(NormalizationForm.FormD)
                .Where(c => CharUnicodeInfo.GetUnicodeCategory(c) != 
                            UnicodeCategory.NonSpacingMark)
                .ToArray());
    }
}
static void Main()
{
    var input = "ŃŅŇ ÀÁÂÃÄÅ ŢŤţť Ĥĥ àáâãäå ńņň";
    var output = input.RemoveDiacritics();
    Debug.Assert(output == "NNN AAAAAA TTtt Hh aaaaaa nnn");
}