Die String-Ähnlichkeit ist die Anzahl der gemeinsamen n-grams durch die Anzahl der auftretenden n-grams zweier Strings s1 und s2.
Für die Suche ist s1 der Suchbegriff und s2 ein Begriff in der Datenbank. Die Suche läßt sich mit invertierten Indizes über die n-grams implementieren.
Da die Anzahl der gemeinsamen n-grams größer 0 sein muß, braucht man nur die Begriffe in der Datenbank suchen, die mindestens ein gemeinsamenes n-gram mit dem Suchbegriff haben. Die Suche nach allen Begriffen in der Datenbank, die eine String-Ähnlichkeit größer 0 haben, kann jedoch sehr aufwendig werden, da in natürlichen Strachen bestimmte n-grams sehr oft vorkommen (z.B. en, nen).
| trigrams | searched word | retrieved words | |
|---|---|---|---|
| RECEIEVE | RECEIVE | RECEIVER | |
| REC | 1 | 1 | 1 |
| ECE | 1 | 1 | 1 |
| CEI | 1 | 1 | 1 |
| EIE | 1 | - | - |
| IEV | 1 | - | - |
| EVE | 1 | - | - |
| EIV | - | 1 | 1 |
| IVE | - | 1 | 1 |
| VER | - | - | 1 |
| Koeffizient | 3/8 | 3/9 | |
In diesem Fall hat das Wort "RECEIVE" eine größere String-Ähnlichkeit (3/8) zu dem falschgeschriebenen Suchbegriff "RECEIEVE" als der Begriff "RECEIVER" (3/9).