SQL Server: Implementierung eines N-Gram Suchindex (de-DE)

Alle aktuellen Web Suchmaschinen haben nur ein Eingabefeld für die Suchkriterien und liefern immer ein Ergebnis, egal was man eingibt.
Das macht uns Entwicklern nun das Leben schwer, denn mittlerweile erwarten die Endanwender dieses auch in Line-of-Business (LOB) Anwendungen, z.B. bei der Suche nach einer Adresse oder eines Artikels. Wie man eine vergleichbare Funktion mit dem MS SQL Servers implementieren kann soll dieser Artikel zeigen.

Einführung

Die Build-In Funktion Volltextindex des Microsoft SQL Server bietet eine einfache Möglichkeit, ganze Worte des Datenbestandes zu indizieren, sowie dieses flexibel und performant abzufragen. Es gibt nur ein paar Einschränkungen, die dazu führen, dass es nicht ganz für eine Websuche ähnliche Funktionalität geeignet ist.

• keine Suffixsuche möglich wie *Teilbegriff

• keine Schreibfehlertoleranz bezüglich Suchbegriff und/oder Daten

• nur bedingte Indizierung von Satztrennzeichen und anderen Noise Words
  Eine Alternative ist es, eine eigene Indizierung zu implementieren und zwar in diesem Fall den sogenannten N-Gram-Index.
  Bei einem N-Gram Index werden immer alle N aufeinander folgende Buchstaben als Einheit (Fragment) gewertet und diese indiziert, wobei N ein beliebiger numerischer Wert von 1-x sein kann.
  Ein Beispiel mit "Hello World" und einem 3-Gram ergibt die Einheiten
  "HEL", "ELL", "LLO", "LO ", "O W", " WO", "WOR", "ORL", "RLD"

---

Normalisierung

Ziel ist es eine fehlertolerante und Akzent-Insensitive Suche von Adressen zu implementieren, dafür muss man die Datenbasis für den N-Gram Index entsprechend normalisiert bereitstellen. Das setzt ein paar Überlegungen vorab voraus.

Umlaute

Deutsche Umlaute wie Ü kann man durch UE ersetzen, so finden man mit dem Suchbegriff "Müller" auch den Namen "Mueller".
In anderen Sprachen gibt es Sonderzeichen, die dem lateinischen Alphabet entstammen und Kennzeichen für die Betonung enthalten, wie das polnische Ł. Solche Zeichen kann man auch ersetzen.

Satztrennzeichen

Beim Volltextindex werden Satztrennzeichen als Wortende gewertet und nicht mit indiziert. Es gibt aber durchaus Firmen- und Produktnamen, die ein Satztrennzeichen beinhalten und somit sollten dies e in einem gewissen Rahmen mit suchbar sein. Hier muss man nach Datenbestand entscheiden, ob die Satztrennzeichen beibehalten oder ersetzt werden sollen.
In diesem Beispiel werden zur Vereinfachung alle Satztrennzeichen durch ein einziges Zeichen ersetzt. So bleibt der Textaufbau erhalten, aber es wird zur Indizierung und Suche nur ein Zeichen verwendet.

Sonderzeichen

Auch hier muss man nach Datenbestand entscheiden, ob man Sonderzeichen ersetzt oder nicht. Gutes Beispiel ist das @ Zeichen bei E-Mail Adressen; möchte man gezielt nur nach der E-Mail Adresse suchen können oder soll nach den Teilen der E-Mail Adresse auch in anderen Datenbereich gesucht werden.

Damit sind in diesem Beispiel nur

• Ziffern

• Lateinische Großbuchstaben

• Ausrufezeichen ! als allgemeiner Ersatz für alle Satztrennzeichen

• Doppelkreuz # als allgemeiner Ersatz für alle anderen Sonderzeichen als Zeichen für den normalisierten Text zugelassen.
  Um die Liste der zulässigen Zeichen zentral pflegen zu können, wird eine Funktion angelegt, die diese zurück liefert; globale Variablen gibt es im MS SQL Server nicht.

  CREATE FUNCTION  dbo.fnGetNGramValidChars()
      RETURNS nvarchar(39)
  AS
  BEGIN
      -- Approved Signs for N-Gram Index
      -- Western capital letters + Space
      -- Digits
      -- Delimiter sign: !
      -- Special character sign: #
      RETURN N'ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789!#';
   
  END;
  

  Alle anderen Zeichen werden entsprechend ersetzt. Dazu wird eine weitere Funktion erstellt, die den übergebenen Text entsprechend normalisiert, sie wird später sowohl für die Indizierung der Daten als auch für die Normalisierung des Suchbegriffes genutzt.
  Hier die gekürzte Version:

  CREATE FUNCTION  dbo.fnNormalizeDatastring
      (@string nvarchar(max))
      RETURNS nvarchar(max)
  AS
  BEGIN
      -- Get all valid characters
      DECLARE @validChars nvarchar(50) = (SELECT dbo.dbo.fnGetNGramValidChars() AS Result);
      -- Only capital characters
      SET @string = UPPER(@string);
      -- Replace umlauts
      SET @string = REPLACE(@string, N'Ä', N'AE');
      SET @string = REPLACE(@string, N'Æ', N'AE');
      -- usw. ...
   
      -- Registered Marks
      SET @string = REPLACE(@string, N'℅', N'C#O');
      SET @string = REPLACE(@string, N'™', N'TM');
      -- usw. ...
   
      -- Replace delimiter by !
      SET @string = REPLACE(@string, N'.', N'!');
      SET @string = REPLACE(@string, N',', N'!');
      -- usw. ...
   
      -- Replace special characeters by hash mark.
      SET @string = REPLACE(@string, N'+', N'#');
      SET @string = REPLACE(@string, N'-', N'#');
      -- usw. ...
   
      -- Replace all other invalid characters by space.
      DECLARE @loop int = 1;
      DECLARE @len int = LEN(@string);
      DECLARE @invalidChar nchar(1);
   
      WHILE @loop <= @len
      BEGIN
          SET @invalidChar = SUBSTRING(@string, @loop, 1);
          IF CHARINDEX(@invalidChar, @validChars) <= 0
          BEGIN
              SET @string = REPLACE(@string, @invalidChar, N' ');
          END;
   
          SET @loop = @loop + 1;
      END;
   
      -- Remove multiple spaces
      DECLARE @goOn tinyint = 1;
      DECLARE @oldLen int;
   
      WHILE @goOn <> 0
      BEGIN
          SET @oldLen = LEN(@string);
          SET @string = REPLACE(@string, N'    ', N' ');
          SET @string = REPLACE(@string, N'  ', N' ');
   
          IF @oldLen = LEN(@string)
          BEGIN
              SET @goOn = 0;
          END;
      END;
   
      RETURN @string;
  END;
  

  Anmerkung: Solche aufwendigen String Operationen sind im SQL Server sehr teuer. Denkbar wäre zur Optimierung eine Implementierung als CLR Assembly.

---

Indexerstellung

Der Index kann einfach über die Anzahl der erlaubten Zeichen, die Position des Zeichens und dem N-Gram Wert errechnet.

Für das Fragment "BDHZ" errechnet sich der Index-Wert beispielhaft so über (Position ist 0-based)
B = Position 1 * (39^0) = 1
D = Position 4 * (39^1) = 156
H = Position 7 * (39^2) = 10.647
Z = Position 25 * (39^3) = 1.482.975
Summe = 1.493.779 abzgl. Integer Untergrenze -2.147.483.648 => Indexwert -2.145.989.869

Nehmen wir als Beispiel eine 4-Gram Index mit den oben definierten 39 Zeichen, da können 39^4 = 2.313.441 Zeichenkombinationen (Fragmente) entstehen.
Lassen wir auch negative Werte zu, reicht der Wertebereich des int Datentypen bis zum 6-Gram Index bequem aus.

Die Anzahl möglicher Indexwerte je N-Gram:
2-Gram = 39^2 = 1.521 => smallint
3-Gram = 39^3 = 59.319 => smallint
4-Gram = 39^4 = 2.313.441 => int
5-Gram = 39^5 = 90.224.199 => int
6-Gram = 39^6 = 3.518.743.761 => int
7-Gram = 39^7 = 137.231.006.679 => bigint

Die Berechnungsfunktion in T-SQL sieht wie folgt aus, wobei davon ausgegangen wird, dass das Fragment normalisiert übergeben wird.

CREATE FUNCTION  dbo.fnCalculate4GramIndex
    (@fragment nchar(4))
    RETURNS int
AS
BEGIN
    -- Get all valid characters
    DECLARE @validChars varchar(50) = (SELECT dbo.fnGetNGramValidChars() AS Result);
    DECLARE @size int  = (SELECT  LEN(@validChars) AS  size);
 
    DECLARE @id int = -2147483648;
    -- Calculate position of each char
    DECLARE @pos1 int = CHARINDEX(SUBSTRING(@fragment, 1, 1), @validChars);
    DECLARE @pos2 int = CHARINDEX(SUBSTRING(@fragment, 2, 1), @validChars);
    DECLARE @pos3 int = CHARINDEX(SUBSTRING(@fragment, 3, 1), @validChars);
    DECLARE @pos4 int = CHARINDEX(SUBSTRING(@fragment, 4, 1), @validChars);
 
    SET @id = @id + (@pos1 - 1) + 
                    (@pos2 - 1) * @size + 
                    (@pos3 - 1) * POWER(@size, 2) + 
                    (@pos4 - 1) * POWER(@size, 3);
 
    RETURN @id;
END;

Um nun alle Index-Werte für einen ganzen Text zu erzeugen, wird eine Table Valued Function (TVF) angelegt, die den Text in die Fragmente zerlegt, die Werte errechnet und das Ergebnis als eine Tabelle zurück liefert.

CREATE FUNCTION  dbo.fnBuildIndex4Gram
    (@string nvarchar(max))
    RETURNS @ids TABLE (id int)
AS
BEGIN
    SET @string = (SELECT dbo.fnNormalizeDatastring(@string));
    DECLARE @pos int = 1;
    DECLARE @len int = LEN(@string) - 4;
 
    IF @len <= 0
        RETURN;
 
    WHILE @pos <= @len
    BEGIN
        INSERT INTO  @ids (id)
        SELECT dbo.fnCalculate4GramIndex(SUBSTRING(@string, @pos, 4));
 
        SET @pos = @pos + 1;
    END
 
    RETURN;
END;
 
-- Small test:
SELECT *
FROM dbo.fnBuildIndex4Gram(N'Hello World') AS  IDX;

Funktioniert soweit.

Als Beispiel für die Indizierung dienen die Adress-Daten im Schema "Person" aus der Datenbank AdventureWorks.
Um alle relevanten Daten in einem Feld zu erhalten, inkl. der 0-n Telefonnummern, wird eine View angelegt, die die Daten bereitstellt. Diese View hat zudem den Vorteil, dass man die Daten jederzeit erweitern kann, ohne weitere Logiken und Prozessschritte anpassen zu müssen.

CREATE VIEW  Person.vAddressIndexData
AS
    SELECT ADR.AddressID,
           ADR.AddressLine1 + N' ' +
           ISNULL(ADR.AddressLine2 + N' ', N'') +  
           ADR.City + N' ' +
           ADR.PostalCode +  N' ' +
           SPR.StateProvinceCode + N' ' +
           SPR.Name + N' '  +
           CR.Name + N' '  +
           ISNULL(PER.Title + N' ', N'') +
           ISNULL(PER.FirstName + N' ', N'') +
           ISNULL(PER.MiddleName + N' ', N'') +  
           ISNULL(PER.LastName + N' ', N'') +
           ISNULL(PER.Suffix + N' ', N'') +
           ISNULL(EA.EmailAddress + N' ', N'') +
           ISNULL((SELECT CAST((SELECT (SELECT PHO.PhoneNumber + ','
                                 FROM Person.PersonPhone AS PHO
                                 WHERE PHO.BusinessEntityID = PER.BusinessEntityID
                                 FOR XML PATH (''), Type 
                               ) AS  ColCSV 
                              ) AS  nvarchar(MAX))) + N' ', N'')
           AS IndexData
    FROM Person.Address AS ADR
         INNER JOIN
         Person.StateProvince AS  SPR
             ON ADR.StateProvinceID = SPR.StateProvinceID
         INNER JOIN
         Person.CountryRegion AS  CR
             ON SPR.CountryRegionCode = CR.CountryRegionCode
         LEFT JOIN
         Person.BusinessEntityAddress AS  BEA
             ON ADR.AddressID = BEA.AddressID
         LEFT JOIN
         Person.Person AS  PER
             ON BEA.BusinessEntityID = PER.BusinessEntityID
         LEFT JOIN
         Person.EmailAddress AS  EA
             ON PER.BusinessEntityID = EA.BusinessEntityID
                AND PER.EmailPromotion = EA.EmailAddressID;

Anmerkung: Die View ist nur als Beispiel gedacht, auf Sinn und Korrektheit wurde hier nicht sonderlich geachtet.

Als nächstes brauchen wir zum Speichern der Indexwerte eine Tabelle. Benötigt wird der Primary Key des Datensatzes, hier die AddressId, und der N-Gram Indexwert. Da ein Fragment/Indexwert je Datensatz mehrfach vorkommen kann, ist ein Feld für die Häufigkeit vorgesehen statt jeden Indexwert einzeln zu speichern; was natürlich auch ging.

CREATE TABLE  dbo.Gram4Index(
    AddressId int  NOT NULL,
    ID_4Gram int  NOT NULL,
    Occurrence smallint  NOT NULL,
    CONSTRAINT PK_Gram4Index PRIMARY KEY  CLUSTERED 
    (
        AddressId ASC,
        ID_4Gram ASC
    )
);

Anmerkung: Die Vermischung von verschiedenen Schemas wie hier ist normalerweise nicht sinnvoll.
Bei der späteren Suchfunktion wird direkt nur der Indexwert benötigt, dazu ist der Primary Key nicht so geeignet, deswegen wird ein weiterer Index angelegt, der selektiver ist. Um unnötige Key Lookups auf die AddressId und Occurrence in der Basis Tabelle zu vermeiden, werden die Felder als Include mit aufgenommen.

CREATE NONCLUSTERED INDEX IDX_Gram4Index_Search
    ON dbo.Gram4Index 
       (ID_4Gram)
    INCLUDE (AddressId, Occurrence);
 
-- Some additional statistics.
 
CREATE STATISTICS  [STAT_Gram4Index_AddressId] 
    ON [dbo].[Gram4Index]
       ([AddressId]);
 
CREATE STATISTICS  [STAT_Gram4Index_Occurrence] 
    ON [dbo].[Gram4Index]
       ([Occurrence]);
 
CREATE STATISTICS  [STAT_Gram4Index_AddressId_Occurrence] 
    ON [dbo].[Gram4Index]
       (AddressId, [Occurrence]);

Wie es sich gehört sollte das Füllen der Index-Wert zentral über ein Stored Procedure erfolgen, die dann aus anderen SP's oder Triggern heraus aufgerufen werden kann.
Die folgende SP erfüllt diesen Zweck, sie löscht zunächst die alte Index-Werte und fügt die Neuen in die Index Tabelle ein; erwartet wird nur der PK AddressId als Parameter.

CREATE PROCEDURE  dbo.spUpdate4Gram
    @addressId int
AS
BEGIN
    SET NOCOUNT ON;
 
    -- Delete old index data
    DELETE FROM  dbo.Gram4Index
    WHERE AddressId  = @addressId;
 
    -- Re-create Index for the Address.
    INSERT INTO  dbo.Gram4Index
       (AddressId, ID_4Gram, Occurrence)
    SELECT ADR.AddressId, NG.ID AS ID_NGram4, COUNT(*) AS  Occurrence
    FROM Person.vAddressIndexData AS ADR
         CROSS APPLY
         dbo.fnBuildIndex4Gram(ADR.IndexData) AS  NG
    WHERE ADR.AddressId = @addressId
    GROUP BY  ADR.AddressId, NG.ID;
END;

Da wir mit der AdventureWorks eine bestehende Datenbank mit vorhandenen Daten haben, brauchen wir zusätzlich noch eine Routine, die Initial die vorhandenen Daten indiziert. Dazu arbeitet man per Cursor alle vorhandenen Adressen ab.

SET NOCOUNT ON;
DECLARE @addressId int;
DECLARE addresses CURSOR LOCAL  FOR
    SELECT AddressId
    FROM Person.Address;
 
OPEN addresses;
 
FETCH NEXT  FROM addresses INTO @addressId;
WHILE (@@FETCH_STATUS = 0)
BEGIN
    EXEC dbo.spUpdate4Gram @addressId;
    FETCH NEXT  FROM addresses INTO @addressId;
END;
 
CLOSE addresses;
DEALLOCATE addresses;
 
PRINT N'Finished';

---

Speicherbedarf für den Index

Jeder Index benötigt zusätzlichen Speicherplatz, das ist bei diesem N-Gram Index natürlich nicht anders.
Bei einem N-Gram Index wird für einen Text der Länge x dann (x - n) Fragmente gebildet. Je Fragment wird

• AddressId = int = 4 Byte

• ID_4Gram = int = 4 Byte

• Occurrence = smallint = 2 Byte

• Primary Key = 8 Byte

• Suchindex = 10 Byte gespeichert, in der Summe alo 28 Bytes je Fragment. Hat ein Text 1.000 Zeichen, kommen bei einem 4-Gram Index also 996 * 28 Bytes = 27.888 Bytes zustande. Im Vergleich benötigt ein einfacher Index auf ein NVarChar Feld 2 Bytes je Zeichen, hier als 2.000 Bytes. Der N-Gram Index ist also ~14-mal so groß und somit vom Speicherplatz her sehr teuer.
  In diesem konkreten Fall werden 30,4 MB für die Daten und 21 MB für die Indizes benötigt, Gesamt also 51,4 MB.

  Anmerkung: Die Größenberechnung ist stark vereinfacht, die genauere Berechnung kann man in der MSDN nachlesen: Schätzen der Größe einer Tabelle

---

Suchlogik

Geeignete Suchtreffer sind nun die Adressen, die möglichst viele der gleichen Indexwerte aufweisen wie im Suchstring. Je weniger Indexwerte übereinstimmen, desto weniger stimmt die Adresse mit dem Suchtext überein.
Im Gegensatz zu einem normalen Index ist die Reihenfolge einzelner Begriff im Suchtext wie auch in den Daten nahezu unerheblich.
Andererseits können natürlich Fragmente aus dem Suchtext auch in völlig anderen Kombinationen in den Daten vorkommen.
Für die Suche wird zunächst der gesamte Suchtext mittels der Funktion dbo.fnBuildIndex4Gram wie zuvor in die einzelnen Indexwerte zerlegt, diese mit den gespeicherten Indexwerten gejoint und nun die Übereinstimmungen gezählt, genauer gesagt wird die Summe über "Occurrence" gebildet und so häufige im Text vorkommende, übereinstimmende Indexwerte stärker gewichtet.
Über den Parameter @factor kann gesteuert werden, wieviele Indexwerte prozentual übereinstimmen müssen, um als Suchergebnis zu gelten. Der Parameter kann Werte zwischen 0.0 und 1.0 haben, je größer der Wert, desto genauer ist das Suchergebis. Verringert man den Faktor, werden auch ungenaue Ergebnisse zurück geliefert, z.B. auch welche mit Schreibfehler.

CREATE PROCEDURE  dbo.spSearch4Gram
    (@search nvarchar(4000),
     @factor decimal(9, 4)
    )
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @len int;
 
    -- Normalize search string.
    SET @search = (SELECT dbo.fnNormalizeDatastring(@search));
    SET @len = (LEN(@search) - 4) * @factor;
    IF @len <= 0
        SET @len = 1;
 
    -- Weighted 4-Gram index search
    ;WITH idx AS
        (SELECT GR4.AddressId, SUM(GR4.Occurrence) AS  Weigth
         FROM dbo.fnBuildIndex4Gram(@search) AS BIG
              INNER JOIN
              dbo.Gram4Index AS  GR4
                  ON GR4.ID_4Gram = BIG.id
         GROUP BY  GR4.AddressId
         HAVING SUM(GR4.Occurrence) > @len
        )
    SELECT ADR.AddressID,
           ADR.AddressLine1,
           ADR.City,
           ADR.City,
           idx.Weigth
    FROM Person.Address AS ADR WITH (NOLOCK)
         INNER JOIN
         idx 
             ON ADR.AddressID = idx.AddressId
    ORDER BY  idx.weigth DESC;
END;
 
-- Test cases
 
-- Umlaut search => "Buergermeister" as result
EXEC dbo.spSearch4Gram N'Saarland Bürgermeister', 0.8;
-- and counter wise
EXEC dbo.spSearch4Gram N'rotthaeuser germany saarbruecken', 0.8;
 
-- City name and telephon number without area code.
EXEC dbo.spSearch4Gram N'Springfield -555-0181', 0.7;
 
-- Typeo: "Bery" instead "Berry"
EXEC dbo.spSearch4Gram N'Bery court', 0.6;
 
-- Some part terms
EXEC dbo.spSearch4Gram N'West gloria California 91791', 0.75;
 
-- Long search text
EXEC dbo.spSearch4Gram N'5157 Washington 98027 lane marywood Issaquah', 0.8;
 
-- Large result set
EXEC dbo.spSearch4Gram N'Washington', 0.8;

---

Zusammenfassung

Der N-Gram Index ist leicht mit Standard Transact-SQL zu implementieren und kann einfach an Besonderheiten des jeweiligen Datenbestandes und der gewünschten Suchlogik angepasst werden.
Die Suchfunktion ist sehr performant und die Genauigkeit oder Toleranz gegenüber Schreibfehlern kann über einen Parameter individuell gesteuert werden sowie über die Wahl des N Wertes.
Diese Vorteile erkauft man sich dafür mit einem hohen Speicherbedarf für die Indexwerte.

Wie bei jeder Lösung kann man auch bei dieser noch Optimierungspotential finden, z.B. die Verwendung eines Column Store Indexes, was aber dann den Einsatz auf die Enterprise Edition einschränkt.

---

Andere Sprachen

SQL Server: Implementation of N-Gram Search Index

---

Weblinks

https://de.wikipedia.org/wiki/N-Gramm
https://en.wikipedia.org/wiki/N-gram