Firebird: Soundex

1 - Vorbereitungen

Schema des SoundexDie unscharfe Suche mittels des Soundex Algorithmus hat schon eine lange Tradition. Sie wurde von Robert Russell entwickelt und bereits 1918 ist das Patent erteilt worden.

Dieser phonetische Algorithmus basiert darauf, verschiedene Zeichen in Gruppen zusammenzufassen und mehrfach aufeinander folgende Zeichen zu eleminieren. Dabei werden nicht alle Zeichen in die Gruppen aufgenommen, die aber trotzdem bei der überprüfung auf mehrfach aufeinander folgende Gruppen berücksichtigt werden. Das erste Zeichen wird immer direkt übernommen. Darauffolgend kommen die ersten drei ermittelten Gruppen. Ist die Länger der resultierende Zeichenfolge kleiner als vier, wird mit "0" auf die Länge vier aufgefüllt.

Der ursprüngliche Soundex Algorithmus ist speziell auf die englische Sprache zugeschnitten, kann in dem hier beschriebenen Verfahren aber leicht an andere Sprachen angepasst werden.

Im Übrigen wird hier ganz bewußt statt von Buchstaben immer von Zeichen geschrieben, da auch Zeichen, die keine Buchstaben sind verarbeitet werden können.

Gruppierung der Zeichen

Die Verteilung der Zeichen auf die einzelnen Gruppen wird in der Tabelle "soundex_weights" vorgenommen. In dieser Tabelle wird zu jedem Zeichen die Gruppe bzw. die Gewichtung gespeichert.

Zusätzlich wird noch hinterlegt, zu welcher Sprache diese Gewichtung gehört. Damit können verschiedene Sprachen mit unterschiedlichen Gewichtungen in einer Datenbank verwendet werden.

Gewichtungen:

  • -1: Das Zeichen wird bei der Ermittlung einer Gruppe ignoriert, aber trotzdem als erstes Zeichen verwendet. Auch alle nicht in die Tabelle aufgenommenen Zeichen werden so behandelt.
  • 0: Das Zeichen wird ebenso bei der Ermittlung einer Gruppe ignoriert. Allerdings werden zwei gleiche Gruppen vor und nach diesem Zeichen nicht zu einer Gruppe zusammengefasst. Auch an erster Stelle wird dieses Zeichen übernommen.
  • 1-9: Diese Zeichen werden wie alle anderen auch an erster Stelle übernommen und bestimmen an den folgenden Positionen die Gruppen.
In der Beispieldatenbank ist die klasische Verteilung für Englisch und eine angepasste Verteilung für Deutsch hinterlegt.
CREATE TABLE "soundex_weights" (
    "sxw_language"   "dom_Lng_Token" NOT NULL,
    "sxw_character"  "dom_SingleChar" NOT NULL,
    "sxw_weight"     "dom_Soundex_Weight" NOT NULL
);

ALTER TABLE "soundex_weights"
  ADD CONSTRAINT "PK_soundex_weights"
  PRIMARY KEY ("sxw_language", "sxw_character");

Das Wort in Zeichen zerlegen

Um die einzelnen Zeichen eines Wortes mit der Tabelle "soundex_weights" zu verknüpfen, wird eine selektierbare STORED PROCEDURE verwendet. Diese SP gibt jedes einzelne Zeichen des übergebenen Wortes und seine Position im Wort mittels SUSPEND an den Aufrufer zurück. Die Position ist wichtig, um in der weiteren Verarbeitung die korrekte Reihenfolge sicherzustellen.
CREATE OR ALTER PROCEDURE "prc_soundex_chars" (
  IN_WORD TYPE OF "dom_Word")
RETURNS (
  OUT_POSITION TYPE OF "dom_INT16",
  OUT_CHAR TYPE OF "dom_SingleChar")
AS
DECLARE VARIABLE L_LENGTH TYPE OF "dom_INT16";
DECLARE VARIABLE L_POSITION TYPE OF "dom_INT16";
DECLARE VARIABLE L_WORD TYPE OF "dom_Word";
BEGIN

  /* Startwerte */
  L_LENGTH = COALESCE(CHAR_LENGTH(IN_WORD), 0);
  IF (L_LENGTH > 0)
  THEN
  BEGIN
    L_POSITION = 1;
    L_WORD     = LOWER(IN_WORD);

    /* Alle Zeichen des Wortes mit Position (1-basiert) ausgeben. */
    WHILE (L_POSITION <= L_LENGTH)
    DO
    BEGIN

      /* Position und Zeichen ausgeben */
      OUT_POSITION = L_POSITION                             ;
      OUT_CHAR     = SUBSTRING(L_WORD FROM L_POSITION FOR 1);
      SUSPEND;

      /* nächste Position */
      L_POSITION = L_POSITION + 1;

    END

  END

END