28.01.2014

Implementierung einer phonetischen Suche nach dem Kölner Algorithmus

Technical Value

Ein regelmäßig auftretendes Problem in großen Datenmengen ist es, mögliche redundante Daten aufzuspüren und zu eliminieren. Man denke hier z.B. an Dubletten im Kundenbestand. Die Schwierigkeit dabei ist, dass diese Dubletten nicht exakt der gleichen Schreibweise folgen müssen. So wäre beispielsweise Thomas Müller, Musterstrasse 12 identisch mit Tomas Mueller, Musterstraße 12.

Um diesem Problem zu begegnen existieren verschiedene Ansätze. Alle beruhen darauf, Zeichenketten mit unterschiedlicher Schreibweise miteinander vergleichbar zu machen. So ist ein Ansatz die Fuzzy-String-Suche oder auch unscharfe Suche, die mit Hilfe verschiedener String-Matching-Algorithmen versucht, eine Zeichenkette in einer längeren Zeichenkette oder einem Text zu finden. Hier spielt die Levenshtein-Distanz eine wichtige Rolle, die die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen angibt, um die erste Zeichenkette in die zweite umzuwandeln (s. http://www.levenshtein.de ).

Eine andere Möglichkeit zum Vergleichen von Zeichenketten ist die phonetische Suche. Hierbei wird mit Hilfe der Phonetik versucht eine klangliche Repräsentation der Zeichenketten zu finden und diese zu vergleichen.

Es gibt verschiedene Verfahren, die sich in ihrer jeweiligen Vorgehensweise unterscheiden. Im SQL Server ist der sogenannte Soundex-Algorithmus bereits als Funktion implementiert, der beliebig lange Zeichenketten immer auf einen vierstelligen alphanumerischen Code reduziert. Dieses Verfahren wurde von Russell Anfang des 20. Jahrhunderts in den USA entwickelt und ist deshalb für die englische Sprache optimiert.

Besser auf die deutsche Sprache zugeschnitten ist die Kölner Phonetik. Diese bildet nach bestimmten Regeln jeden Buchstaben eines Wortes auf eine Ziffer zwischen 0 und 8 ab. Die Länge des phonetischen Codes ist dabei im Gegensatz zum Soundex nicht beschränkt (s. http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik ). Eine mögliche Implementierung der Kölner Phonetik als Funktion für den SQL Server 2012 soll hier vorgestellt werden.

  1. CREATE FUNCTION [dbo].[SOUNDEX_GER] (@strWord NVARCHAR(1000))
  2. RETURNS NVARCHAR(1000) AS
  3. BEGIN
  4.  
  5. DECLARE
  6.        @Word NVARCHAR(1000),
  7.        @WordLen int,
  8.        @Code NVARCHAR(1000) = '',
  9.        @PhoneticCode NVARCHAR(1000) = '',
  10.        @index int,
  11.        @RegEx NVARCHAR(50),
  12.        @previousCharval nvarchar(1) = '|',
  13.        @Charval nvarchar(1)
  14.  
  15.    SET @Word = lower(@strWord);
  16.    IF len(@Word) < 1
  17.       RETURN 0;
  18.  
  19.     -- Umwandlung:
  20.     -- v->f, w->f, j->i, y->i, ph->f, ä->a, ö->o, ü->u, ß->ss, é->e, è->e, à->a, ç->c
  21.  
  22.     SET @Word = REPLACE(
  23.         REPLACE(
  24.           REPLACE(
  25.             REPLACE(
  26.               REPLACE(
  27.                 REPLACE(
  28.                   REPLACE(
  29.                     REPLACE(
  30.                       REPLACE(
  31.                         REPLACE(
  32.                           REPLACE(
  33.                             REPLACE(
  34.                               REPLACE(
  35.                                 REPLACE(
  36.                                   REPLACE(@Word,'v','f'),
  37.                                 'w','f'),
  38.                               'j','i'),
  39.                             'y','i'),
  40.                           'ä','a'),
  41.                         'ö','o'),
  42.                       'ü','u'),
  43.                     'é','e'),
  44.                   'è','e'),
  45.                 'ê','e'),
  46.               'à','a'),
  47.             'á','a'),
  48.           'ç','c'),
  49.         'ph','f'),
  50.         'ß','ss');
  51.  
  52.       -- Zahlen und Sonderzeichen entfernen
  53.  
  54.        SET @RegEx = '%[^a-z]%';
  55.        WHILE PatIndex(@RegEx, @Word) > 0
  56.            SET @Word = Stuff(@Word, PatIndex(@RegEx, @Word), 1, '');
  57.  
  58.  
  59.      -- Bei Strings der Länge 1 wird ein Leerzeichen angehängt,
  60.      -- um die Anlautprüfung auf den zweiten Buchstaben zu ermöglichen.
  61.  
  62.     SET @WordLen = LEN(@Word);
  63.     IF @WordLen = 1
  64.         SET @Word += ' ';
  65.  
  66.     -- Sonderfälle am Wortanfang
  67.  
  68.     IF (substring(@Word,1,1) = 'c')
  69.    BEGIN
  70.    -- vor a,h,k,l,o,q,r,u,x
  71.             SET @Code =
  72.                   CASE
  73.                       WHEN substring(@Word,2,1) IN ('a','h','k','l','o','q','r','u','x')
  74.                          THEN '4'
  75.                          ELSE '8'
  76.                    END;
  77.            SET @index = 2
  78.        END
  79.    ELSE
  80.       SET @index = 1;
  81.  
  82.  
  83.    -- Codierung    
  84.  
  85.    WHILE @index <= @WordLen
  86.    BEGIN
  87.         SET @Code =
  88.            CASE
  89.               WHEN substring(@Word,@index,1) in ('a','e','i','o','u')
  90.                   THEN @Code + '0'
  91.               WHEN substring(@Word,@index,1) = 'b'
  92.                   THEN @Code + '1'
  93.               WHEN substring(@Word,@index,1) = 'p'
  94.                   THEN IIF (@index < @WordLen, IIF(substring(@Word,@index+1,1) = 'h', @Code+'3', @Code+'1'), @Code+'1')
  95.               WHEN substring(@Word,@index,1) in ('d','t')
  96.                   THEN IIF (@index < @WordLen, IIF(substring(@Word,@index+1,1) in ('c','s','z'), @Code+'8', @Code+'2'), @Code+'2')
  97.               WHEN substring(@Word,@index,1) = 'f'
  98.                   THEN @Code + '3'
  99.               WHEN substring(@Word,@index,1) in ('g','k','q')
  100.                   THEN @Code + '4'
  101.               WHEN substring(@Word,@index,1) = 'c'
  102.                   THEN IIF (@index < @WordLen, IIF(substring(@Word,@index+1,1) in ('a','h','k','o','q','u','x'), IIF(substring(@Word,@index-1,1) = 's' or substring(@Word,@index-1,1) = 'z', @Code+'8', @Code+'4'), @Code+'8'), @Code+'8')
  103.               WHEN substring(@Word,@index,1) = 'x'
  104.                   THEN IIF (@index > 1, IIF(substring(@Word,@index-1,1) in ('c','k','x'), @Code+'8', @Code+'48'), @Code+'48')
  105.               WHEN substring(@Word,@index,1) = 'l'
  106.                   THEN @Code + '5'
  107.               WHEN substring(@Word,@index,1) = 'm' or substring(@Word,@index,1) = 'n'
  108.                   THEN @Code + '6'
  109.               WHEN substring(@Word,@index,1) = 'r'
  110.                   THEN @Code + '7'
  111.               WHEN substring(@Word,@index,1) = 's' or substring(@Word,@index,1) = 'z'
  112.                   THEN @Code + '8'
  113.               ELSE @Code
  114.          END;
  115.          SET @index += 1;
  116.      END
  117.  
  118.  
  119.    -- die mehrfachen Codes entfernen und erst dann die „0“ eliminieren
  120.    -- Am Wortanfang bleiben „0“-Codes erhalten
  121.  
  122.    SET @index = 0;
  123.    WHILE @index < LEN(@code)
  124.    BEGIN
  125.       SET @charval = SUBSTRING(@code, @index+1, 1);
  126.       IF @charval <> @previousCharval
  127.       BEGIN
  128.          IF @charval <> '0' OR @index = 0
  129.          BEGIN  
  130.              SET @PhoneticCode += @charval;
  131.          END  
  132.      END
  133.      SET @previousCharval = @charval;
  134.      SET @index += 1;
  135.    END  
  136.  RETURN @PhoneticCode;
  137.  
  138.  END;

Ein möglicher Anwendungsfall für diese Funktion ist die Datenqualitätsverbesserung durch oben angesprochene Dublettenbereinigung im Datenbestand. Hier kann beispielsweise ein manuelles Screening auf Dubletten durch die Fachabteilung bzw. einen Data Steward im Rahmen eines Master Data Management erfolgen.

Teilen auf

Newsletter Anmeldung

Abonnieren Sie unseren Newsletter!
Lassen Sie sich regelmäßig über alle Neuigkeiten rundum ORAYLIS und die BI- & Big-Data-Branche informieren.

Jetzt anmelden