distanza Levenshtein in T-SQL

Question

Sono interessato all'algoritmo T-SQL che calcola la distanza di Levenshtein.

Answer 1

Arnold Fribble proposes questo:

SET QUOTED_IDENTIFIER ON 
GO 
SET ANSI_NULLS ON 
GO 

CREATE FUNCTION edit_distance_within(@s nvarchar(4000), @t nvarchar(4000), @d int) 
RETURNS int 
AS 
BEGIN 
    DECLARE @sl int, @tl int, @i int, @j int, @sc nchar, @c int, @c1 int, 
    @cv0 nvarchar(4000), @cv1 nvarchar(4000), @cmin int 
    SELECT @sl = LEN(@s), @tl = LEN(@t), @cv1 = '', @j = 1, @i = 1, @c = 0 
    WHILE @j <= @tl 
    SELECT @cv1 = @cv1 + NCHAR(@j), @j = @j + 1 
    WHILE @i <= @sl 
    BEGIN 
    SELECT @sc = SUBSTRING(@s, @i, 1), @c1 = @i, @c = @i, @cv0 = '', @j = 1, @cmin = 4000 
    WHILE @j <= @tl 
    BEGIN 
     SET @c = @c + 1 
     SET @c1 = @c1 - CASE WHEN @sc = SUBSTRING(@t, @j, 1) THEN 1 ELSE 0 END 
     IF @c > @c1 SET @c = @c1 
     SET @c1 = UNICODE(SUBSTRING(@cv1, @j, 1)) + 1 
     IF @c > @c1 SET @c = @c1 
     IF @c < @cmin SET @cmin = @c 
     SELECT @cv0 = @cv0 + NCHAR(@c), @j = @j + 1 
    END 
    IF @cmin > @d BREAK 
    SELECT @cv1 = @cv0, @i = @i + 1 
    END 
    RETURN CASE WHEN @cmin <= @d AND @c <= @d THEN @c ELSE -1 END 
END 
GO 

Answer 2

IIRC, con SQL Server 2005 e in seguito è possibile scrivere procedure in qualsiasi linguaggio .NET memorizzato: Using CLR Integration in SQL Server 2005. Con ciò non dovrebbe essere difficile scrivere una procedura per il calcolo di .

Un semplice Hello, World! estratto dal aiuto:

using System; 
using System.Data; 
using Microsoft.SqlServer.Server; 
using System.Data.SqlTypes; 

public class HelloWorldProc 
{ 
    [Microsoft.SqlServer.Server.SqlProcedure] 
    public static void HelloWorld(out string text) 
    { 
     SqlContext.Pipe.Send("Hello world!" + Environment.NewLine); 
     text = "Hello world!"; 
    } 
} 

Poi, nel tuo SQL Server eseguire il seguente:

CREATE ASSEMBLY helloworld from 'c:\helloworld.dll' WITH PERMISSION_SET = SAFE 

CREATE PROCEDURE hello 
@i nchar(25) OUTPUT 
AS 
EXTERNAL NAME helloworld.HelloWorldProc.HelloWorld 

E ora è possibile testare eseguirlo:

DECLARE @J nchar(25) 
EXEC hello @J out 
PRINT @J 

Spero che questo aiuti.

Answer 3

È possibile utilizzare Levenshtein Distanza Algoritmo per il confronto di stringhe

Qui potete trovare un esempio T-SQL a http://www.kodyaz.com/articles/fuzzy-string-matching-using-levenshtein-distance-sql-server.aspx

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999)) 
RETURNS int 
AS 
BEGIN 
DECLARE @s1_len int, @s2_len int 
DECLARE @i int, @j int, @s1_char nchar, @c int, @c_temp int 
DECLARE @cv0 varbinary(8000), @cv1 varbinary(8000) 

SELECT 
    @s1_len = LEN(@s1), 
    @s2_len = LEN(@s2), 
    @cv1 = 0x0000, 
    @j = 1, @i = 1, @c = 0 

WHILE @j <= @s2_len 
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1 

WHILE @i <= @s1_len 
BEGIN 
    SELECT 
    @s1_char = SUBSTRING(@s1, @i, 1), 
    @c = @i, 
    @cv0 = CAST(@i AS binary(2)), 
    @j = 1 

    WHILE @j <= @s2_len 
    BEGIN 
    SET @c = @c + 1 
    SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) + 
    CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END 
    IF @c > @c_temp SET @c = @c_temp 
    SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1 
    IF @c > @c_temp SET @c = @c_temp 
    SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1 
END 

SELECT @cv1 = @cv0, @i = @i + 1 
END 

RETURN @c 
END 

(funzione sviluppata da Joseph Gama)

Uso:

select 
dbo.edit_distance('Fuzzy String Match','fuzzy string match'), 
dbo.edit_distance('fuzzy','fuzy'), 
dbo.edit_distance('Fuzzy String Match','fuzy string match'), 
dbo.edit_distance('levenshtein distance sql','levenshtein sql server'), 
dbo.edit_distance('distance','server') 

L'algoritmo si ripresenta semplicemente ns il numero di stpe per cambiare una stringa in un'altra sostituendo un carattere diverso in un passo

Answer 4

Ho implementato la funzione standard di modifica di Levenshtein in TSQL con diverse ottimizzazioni che migliorano la velocità rispetto alle altre versioni di cui sono a conoscenza. Nei casi in cui le due stringhe hanno caratteri in comune all'inizio (prefisso condiviso), caratteri in comune alla fine (suffisso condiviso) e quando le stringhe sono grandi e viene fornita una distanza di modifica massima, il miglioramento della velocità è significativo. Ad esempio, quando gli input sono due stringhe di 4000 caratteri molto simili e viene specificata una distanza di modifica massima di 2, questa è quasi tre ordini di grandezza più veloce della funzione edit_distance_within nella risposta accettata, restituendo la risposta in 0,073 secondi (73 millisecondi) contro 55 secondi. È anche efficiente in termini di memoria, utilizzando lo spazio uguale alla più grande delle due stringhe di input più uno spazio costante. Usa un singolo "array" nvarchar che rappresenta una colonna e fa tutti i calcoli sul posto, oltre a alcune variabili int helper.

Ottimizzazioni:

• cassonetti trattamento dei prefisso condiviso e/o suffisso
• rientro anticipato se la stringa inizia o grandi finisce con l'intera stringa più piccola
• rientro anticipato se la differenza di dimensioni garantisce distanza massima sarà superato
• utilizza solo un singolo array che rappresenta una colonna nella matrice (implementata come nvarchar)
• quando viene assegnata una distanza massima, la complessità del tempo passa da (len1 * len2) a (min (len1, len2)), ad es.lineare
• quando viene data una distanza massima, all'inizio di ritorno non appena distanza massima vincolato non è noto per essere realizzabile

Le ottimizzazioni sono descritti in maggiore dettaglio in my blog post su Levenshtein in TSQL e un link lì in un altro post con un'implementazione simile a Damerau-Levenshtein. Ma ecco il codice (aggiornato 2014/01/20 per accelerarlo un po 'di più):

-- ============================================= 
-- Computes and returns the Levenshtein edit distance between two strings, i.e. the 
-- number of insertion, deletion, and sustitution edits required to transform one 
-- string to the other, or NULL if @max is exceeded. Comparisons use the case- 
-- sensitivity configured in SQL Server (case-insensitive by default). 
-- http://blog.softwx.net/2014/12/optimizing-levenshtein-algorithm-in-tsql.html 
-- 
-- Based on Sten Hjelmqvist's "Fast, memory efficient" algorithm, described 
-- at http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm, 
-- with some additional optimizations. 
-- ============================================= 
CREATE FUNCTION [dbo].[Levenshtein](
    @s nvarchar(4000) 
    , @t nvarchar(4000) 
    , @max int 
) 
RETURNS int 
WITH SCHEMABINDING 
AS 
BEGIN 
    DECLARE @distance int = 0 -- return variable 
      , @v0 nvarchar(4000)-- running scratchpad for storing computed distances 
      , @start int = 1  -- index (1 based) of first non-matching character between the two string 
      , @i int, @j int  -- loop counters: i for s string and j for t string 
      , @diag int   -- distance in cell diagonally above and left if we were using an m by n matrix 
      , @left int   -- distance in cell to the left if we were using an m by n matrix 
      , @sChar nchar  -- character at index i from s string 
      , @thisJ int   -- temporary storage of @j to allow SELECT combining 
      , @jOffset int  -- offset used to calculate starting value for j loop 
      , @jEnd int   -- ending value for j loop (stopping point for processing a column) 
      -- get input string lengths including any trailing spaces (which SQL Server would otherwise ignore) 
      , @sLen int = datalength(@s)/datalength(left(left(@s, 1) + '.', 1)) -- length of smaller string 
      , @tLen int = datalength(@t)/datalength(left(left(@t, 1) + '.', 1)) -- length of larger string 
      , @lenDiff int  -- difference in length between the two strings 
    -- if strings of different lengths, ensure shorter string is in s. This can result in a little 
    -- faster speed by spending more time spinning just the inner loop during the main processing. 
    IF (@sLen > @tLen) BEGIN 
     SELECT @v0 = @s, @i = @sLen -- temporarily use v0 for swap 
     SELECT @s = @t, @sLen = @tLen 
     SELECT @t = @v0, @tLen = @i 
    END 
    SELECT @max = ISNULL(@max, @tLen) 
     , @lenDiff = @tLen - @sLen 
    IF @lenDiff > @max RETURN NULL 

    -- suffix common to both strings can be ignored 
    WHILE(@sLen > 0 AND SUBSTRING(@s, @sLen, 1) = SUBSTRING(@t, @tLen, 1)) 
     SELECT @sLen = @sLen - 1, @tLen = @tLen - 1 

    IF (@sLen = 0) RETURN @tLen 

    -- prefix common to both strings can be ignored 
    WHILE (@start < @sLen AND SUBSTRING(@s, @start, 1) = SUBSTRING(@t, @start, 1)) 
     SELECT @start = @start + 1 
    IF (@start > 1) BEGIN 
     SELECT @sLen = @sLen - (@start - 1) 
      , @tLen = @tLen - (@start - 1) 

     -- if all of shorter string matches prefix and/or suffix of longer string, then 
     -- edit distance is just the delete of additional characters present in longer string 
     IF (@sLen <= 0) RETURN @tLen 

     SELECT @s = SUBSTRING(@s, @start, @sLen) 
      , @t = SUBSTRING(@t, @start, @tLen) 
    END 

    -- initialize v0 array of distances 
    SELECT @v0 = '', @j = 1 
    WHILE (@j <= @tLen) BEGIN 
     SELECT @v0 = @v0 + NCHAR(CASE WHEN @j > @max THEN @max ELSE @j END) 
     SELECT @j = @j + 1 
    END 

    SELECT @jOffset = @max - @lenDiff 
     , @i = 1 
    WHILE (@i <= @sLen) BEGIN 
     SELECT @distance = @i 
      , @diag = @i - 1 
      , @sChar = SUBSTRING(@s, @i, 1) 
      -- no need to look beyond window of upper left diagonal (@i) + @max cells 
      -- and the lower right diagonal (@i - @lenDiff) - @max cells 
      , @j = CASE WHEN @i <= @jOffset THEN 1 ELSE @i - @jOffset END 
      , @jEnd = CASE WHEN @i + @max >= @tLen THEN @tLen ELSE @i + @max END 
     WHILE (@j <= @jEnd) BEGIN 
      -- at this point, @distance holds the previous value (the cell above if we were using an m by n matrix) 
      SELECT @left = UNICODE(SUBSTRING(@v0, @j, 1)) 
       , @thisJ = @j 
      SELECT @distance = 
       CASE WHEN (@sChar = SUBSTRING(@t, @j, 1)) THEN @diag     --match, no change 
        ELSE 1 + CASE WHEN @diag < @left AND @diag < @distance THEN @diag --substitution 
            WHEN @left < @distance THEN @left     -- insertion 
            ELSE @distance          -- deletion 
           END END 
      SELECT @v0 = STUFF(@v0, @thisJ, 1, NCHAR(@distance)) 
       , @diag = @left 
       , @j = case when (@distance > @max) AND (@thisJ = @i + @lenDiff) then @jEnd + 2 else @thisJ + 1 end 
     END 
     SELECT @i = CASE WHEN @j > @jEnd + 1 THEN @sLen + 1 ELSE @i + 1 END 
    END 
    RETURN CASE WHEN @distance <= @max THEN @distance ELSE NULL END 
END 

Answer 5

ero alla ricerca di un esempio di codice per l'algoritmo Levenshtein, troppo, ed era felice di trovare qui. Ovviamente volevo capire come funziona l'algoritmo e stavo giocando un po 'con uno degli esempi sopra riportati che stavo giocando un pochino che è stato pubblicato da Veve. Al fine di ottenere una migliore comprensione del codice ho creato un EXCEL con Matrix.

distance for FUZZY compared with FUZY

Immagini dicono più di 1000 parole.

Con questo EXCEL ho scoperto che era possibile ottimizzare ulteriormente le prestazioni. Non è necessario calcolare tutti i valori nell'area rossa in alto a destra. Il valore di ciascuna cella rossa risulta nel valore della cella di sinistra più 1. Questo perché la seconda stringa sarà sempre più lunga in quell'area rispetto alla prima, cosa che aumenta la distanza del valore di 1 per ciascun carattere.

si può riflettere che utilizzando l'istruzione IF @j < = @i e aumentando il valore di @i Prima di questa dichiarazione.

CREATE FUNCTION [dbo].[f_LevenshteinDistance](@s1 nvarchar(3999), @s2 nvarchar(3999)) 
    RETURNS int 
    AS 
    BEGIN 
     DECLARE @s1_len int; 
     DECLARE @s2_len int; 
     DECLARE @i  int; 
     DECLARE @j  int; 
     DECLARE @s1_char nchar; 
     DECLARE @c  int; 
     DECLARE @c_temp int; 
     DECLARE @cv0  varbinary(8000); 
     DECLARE @cv1  varbinary(8000); 

     SELECT 
      @s1_len = LEN(@s1), 
      @s2_len = LEN(@s2), 
      @cv1 = 0x0000 , 
      @j  = 1  , 
      @i  = 1  , 
      @c  = 0 

     WHILE @j <= @s2_len 
      SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1; 

      WHILE @i <= @s1_len 
      BEGIN 
       SELECT 
        @s1_char = SUBSTRING(@s1, @i, 1), 
        @c  = @i     , 
        @cv0  = CAST(@i AS binary(2)), 
        @j  = 1; 

       SET @i = @i + 1; 

       WHILE @j <= @s2_len 
        BEGIN 
         SET @c = @c + 1; 

         IF @j <= @i 
         BEGIN 
          SET @c_temp = CAST(SUBSTRING(@cv1, @j + @j - 1, 2) AS int) + CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END; 
          IF @c > @c_temp SET @c = @c_temp 
          SET @c_temp = CAST(SUBSTRING(@cv1, @j + @j + 1, 2) AS int) + 1; 
          IF @c > @c_temp SET @c = @c_temp; 
         END; 
         SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1; 
        END; 
       SET @cv1 = @cv0; 
      END; 
     RETURN @c; 
    END; 

Answer 6

Lasciatemi premettere che so che è terribile. Comunque, sto usando HIVE QL e non conosco abbastanza java per un udf ... Così ho creato il mostro di andy-shtein ... Non è decisamente carino ma in un pizzico penso che sia un suono. Cosa ne pensi?

DECLARE @A VARCHAR(20),@B VARCHAR(20) 
    SET @A = 'AAIRAA' 
    SET @B = 'ALASKA AIR' 
    SELECT 
    CASE WHEN RUNME = 0 THEN 0 ELSE 
    (SUM(CASE WHEN A13 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13 
     WHEN A12 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12 
     WHEN A11 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11 
     WHEN A10 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10 
     WHEN A9 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9 
     WHEN A8 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8 
     WHEN A7 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7 
     WHEN A6 IS NOT NULL THEN A1+A2+A3+A4+A5+A6 
     WHEN A5 IS NOT NULL THEN A1+A2+A3+A4+A5 
     WHEN A4 IS NOT NULL THEN A1+A2+A3+A4 
     WHEN A3 IS NOT NULL THEN A1+A2+A3 
     WHEN A2 IS NOT NULL THEN A1+A2 
     WHEN A1 IS NOT NULL THEN A1 
     ELSE 0 END)*1.0)/ 
    ((13-SUM(CASE WHEN A13 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A12 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A11 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A10 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A9 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A8 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A7 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A6 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A5 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A4 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A3 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A2 IS NULL THEN 1 ELSE 0 END + 
     CASE WHEN A1 IS NULL THEN 1 ELSE 0 END))*1.0) 
     END AS MATCHY 

    FROM (
     SELECT 
     CASE WHEN LEN(@A) < 6 THEN 0 
      WHEN LEN(@B) < 6 THEN 0 
      ELSE 1 END AS RUNME, 
     CASE WHEN SUBSTRING(@A, 1, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 1, 3), '%') THEN 1 ELSE 0 END AS A1, 
     CASE WHEN SUBSTRING(@A, 2, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 2, 3), '%') THEN 1 ELSE 0 END AS A2, 
     CASE WHEN SUBSTRING(@A, 3, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 3, 3), '%') THEN 1 ELSE 0 END AS A3, 
     CASE WHEN SUBSTRING(@A, 4, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 4, 3), '%') THEN 1 ELSE 0 END AS A4, 
     CASE WHEN SUBSTRING(@A, 5, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 5, 3), '%') THEN 1 ELSE 0 END AS A5, 
     CASE WHEN SUBSTRING(@A, 6, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 6, 3), '%') THEN 1 ELSE 0 END AS A6, 
     CASE WHEN SUBSTRING(@A, 7, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 7, 3), '%') THEN 1 ELSE 0 END AS A7, 
     CASE WHEN SUBSTRING(@A, 8, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 8, 3), '%') THEN 1 ELSE 0 END AS A8, 
     CASE WHEN SUBSTRING(@A, 9, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 9, 3), '%') THEN 1 ELSE 0 END AS A9, 
     CASE WHEN SUBSTRING(@A, 10, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 10, 3), '%') THEN 1 ELSE 0 END AS A10, 
     CASE WHEN SUBSTRING(@A, 11, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 11, 3), '%') THEN 1 ELSE 0 END AS A11, 
     CASE WHEN SUBSTRING(@A, 12, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 12, 3), '%') THEN 1 ELSE 0 END AS A12, 
     CASE WHEN SUBSTRING(@A, 13, 3) ='' THEN NULL 
      WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 13, 3), '%') THEN 1 ELSE 0 END AS A13 
    )SUB 
    GROUP BY RUNME 

Answer 7

In TSQL il modo migliore e più veloce per confrontare due elementi sono le istruzioni SELECT che uniscono tabelle su colonne indicizzate. Ecco perché suggerisco di implementare la distanza di modifica se si desidera beneficiare dei vantaggi di un motore RDBMS. Anche i loop TSQL funzioneranno, ma i calcoli della distanza di Levenstein saranno più veloci in altri linguaggi rispetto a TSQL per i confronti di grandi volumi.

Ho implementato la distanza di modifica in diversi sistemi utilizzando serie di join contro tabelle temporanee progettate solo a tale scopo. Richiede alcune pesanti fasi di pre-elaborazione - la preparazione delle tabelle temporanee - ma funziona molto bene con un numero elevato di confronti.

In poche parole: la pre-elaborazione consiste nel creare, compilare e indicizzare tabelle temporanee. Il primo contiene ID di riferimento, una colonna di una lettera e una colonna di charindex. Questa tabella è popolata dall'esecuzione di una serie di query di inserimento che dividono ogni parola in lettere (utilizzando SELECT SUBSTRING) per creare un numero di righe pari a tutte le righe della parola nell'elenco sorgente (lo so, sono molte righe ma SQL server può gestire miliardi di righe). Quindi crea una seconda tabella con una colonna di 2 lettere, un'altra con una colonna di 3 lettere, ecc. I risultati finali sono una serie di tabelle che contengono id di riferimento e sottostringhe di ciascuna parola, oltre al riferimento della loro posizione nella parola.

Una volta eseguita questa operazione, l'intero gioco consiste nel duplicare queste tabelle e unirle contro il loro duplicato in una query di selezione GROUP BY che conta il numero di corrispondenze. Questo crea una serie di misure per ogni possibile coppia di parole, che vengono poi riaggregate in una singola distanza di Levenstein per coppia di parole.

Tecnicamente questo è molto diverso dalla maggior parte delle altre implementazioni della distanza di Levenstein (o delle sue varianti) quindi è necessario capire profondamente come funziona la distanza di Levenstein e perché è stata progettata così com'è. Studia anche le alternative perché con quel metodo ti ritrovi con una serie di metriche sottostanti che possono aiutare a calcolare molte varianti della distanza di editing allo stesso tempo, fornendoti interessanti miglioramenti potenziali di apprendimento automatico.

Un altro punto già menzionato dalle precedenti risposte in questa pagina: provare a preelaborare il più possibile per eliminare le coppie che non richiedono la misurazione della distanza. Ad esempio, una coppia di due parole che non hanno una singola lettera in comune dovrebbe essere esclusa, perché la distanza di modifica può essere ottenuta dalla lunghezza delle stringhe. O non misurare la distanza tra due copie della stessa parola, poiché è 0 per natura. O rimuovere i duplicati prima di eseguire la misurazione, se l'elenco di parole proviene da un testo lungo è probabile che le stesse parole vengano visualizzate più di una volta, quindi misurare la distanza solo una volta farà risparmiare tempo di elaborazione, ecc.