Diakritische tekens en Soundex in .NET nl

Door creator1988 op dinsdag 14 december 2010 12:17 - Reacties (3)
Categorie: Algoritmes, Views: 5.130

In Nederland kennen we zo'n 240.000 geografische entiteiten (straten, buurten, plaatsen, gemeentes, etc.) die gebruik maken van NEN-norm 5825 voor de officile schrijfwijze. Een norm waarin gn diakritische tekens mogen worden gebruikt. So far so good.

Wikipedia over diakrieten: Een diakritisch teken is een teken dat boven, onder of door een letter gezet wordt en nodig is voor de uitspraak. Met diakritische tekens kunnen verschillende aspecten van de uitspraak worden aangegeven. Voorbeelden hiervan zijn de tekens op , , .

Zelfde data, andere schrijfwijze?
So far so good, tot het CBS met een nieuwe aanlevering van buurtinformatie komt. Een groot Excel document waarin ze de schrijfwijze van buurten zoals de gemeente deze hanteert overnemen; waar uiteraard wl diakritische tekens kunnen voorkomen. Gevolg: problemen bij het koppelen van de nieuwe CBS-data, aan onze bestaande data.

Normalisatietijd dus!



Normaliseren van buurt- en gemeentenamen tussen twee datasets
1. Vind alle buurt / gemeente combinaties die direct matchen.
2. Verwijder diakritische tekens, en herhaal 1.
3. Nog niet gelukt? Gebruik het fonetische algoritme Soundex om overeenkomstige gebieden te vinden.

Nu hebben we voor bovenstaande stappen wel wat code nodig:

Diakrieten verwijderen in C#
Unicode kent een aantal schrijfwijzen; waarin de output hetzelfde is, maar de binaire representatie hetzelfde. Deze staan beschreven in de Unicode Normalization Forms. FormD is voor het verwijderen van diakritische tekens erg handig, omdat hierin het teken wordt gerepresenteerd als 2 karakters: de 'u', en de toevoeging '^' als los karakter met een eigen unicode teken. In .NET is voor het normalizeren van Unicode de functie 'Normalize' beschikbaar, waarin ook FormD beschikbaar is.


C#:
1
2
3
4
string q = "Wnseradiel";
char[] normalised = q.Normalize(NormalizationForm.FormD).ToCharArray();
q = new string(normalised.Where(c => (int) c <= 127).ToArray());
// q == "Wunseradiel"



Soundex in C#
Soundex is een fonetisch algoritme dat gebruikt kan worden om 2 strings te vergelijken op uitspraak. In de meeste SQL dialecten is een vorm van dit algoritme beschikbaar, maar meestal in het Engels. Daarom hieronder een Nederlandse versie van Soundex, op basis van een artikel van D. Patrick Caldwell.

C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
var a = DutchSoundex("Overeisel"); // O4070205
var b = DutchSoundex("Overrijssel"); // O4070205
// omg! A en B zijn gelijk! It's magic!

private static Regex simplify = new Regex(@"(\d)\1*D?\1+", RegexOptions.Compiled);

public string DutchSoundex(string s)
{
    // encoding info, e.g. M heeft waarde 6
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string codes = "01230420002566012723044802";

    // karakters vervangen
    Dictionary<string, string> replacements = new Dictionary<string, string>()
                                                  {
                                                      {"QU", "KW"},
                                                      {"SCH", "SEE"},
                                                      {"KS", "XX"},
                                                      {"KX", "XX"},
                                                      {"KC", "KK"},
                                                      {"CK", "KK"},
                                                      {"DT", "TT"},
                                                      {"TD", "TT"},
                                                      {"CH", "GG"},
                                                      {"SZ", "SS"},
                                                      {"IJ", "YY"}
                                                  };

    s = s.ToUpper();

    // vervang de waardes in de dictionary
    foreach (var replacementRule in replacements)
        s = s.Replace(replacementRule.Key, replacementRule.Value);

    StringBuilder coded = new StringBuilder();

    // bereken de waardes op basis van de encoding array
    for (int i = 0; i < s.Length; i++)
    {
        int index = chars.IndexOf(s[i]);
        if (index >= 0)
            coded.Append(codes[index]);
    }

    string result = coded.ToString();

    // repeating karakters vervangen
    result = simplify.Replace(result, "$1").Substring(1);

    // return the first character followed by the coded string
    return string.Format("{0}{1}", s[0], result);
}



Op basis van regel 2. en 3. hebben we 94% van de probleemgevallen automatisch kunnen fixen!

Volgende: Expression Trees - Espresso voor je code! 12-'10 Expression Trees - Espresso voor je code!
Volgende: Internet Explorer 6 / 7 en onverklaarbaar CPU gebruik 12-'10 Internet Explorer 6 / 7 en onverklaarbaar CPU gebruik

Reacties


Door Tweakers user -RetroX-, dinsdag 14 december 2010 12:32

Mooie functie.

Welke plaatsen leverden nog verrassende problemen op?

[Reactie gewijzigd op dinsdag 14 december 2010 12:35]


Door Tweakers user RobIII, dinsdag 14 december 2010 13:42

Hou er wel rekening mee dat soundex primair voor engelstalige doeleinden bedoeld is; waarmee ik dus wil zeggen dat voor de hand liggende matches alsnog wellicht niet gevonden kunnen worden. Oh, en de meeste RDBMS'en kennen native al een soundex ;)
Echt... heb nog stront in mijn ogen volgens mij :X DutchSoundex()


Overigens heb je in je comments dan weer NL dan weer EN :P

[Reactie gewijzigd op dinsdag 14 december 2010 13:51]


Door Tweakers user creator1988, woensdag 15 december 2010 10:26

-RetroX- schreef op dinsdag 14 december 2010 @ 12:32:
Mooie functie.

Welke plaatsen leverden nog verrassende problemen op?
1. Friese buurten waarin de naam in Fries werd aangeleverd door het CBS, en bij ons in het Nederlands staat. Haast onmogelijk om geautomatiseerd te fixen.
2. Buurtnamen die heel erg op elkaar lijken in eenzelfde gemeente (wel in verschillende plaatsen). Ik kan me een specifiek geval herinneren waarin bij ons de buurt eindigde op 'dael', en in CBS data twee keer voorkwam als 'daal' en 'deel'.

Reageren is niet meer mogelijk