Forum und email
Strings
PHP Manual

levenshtein

(PHP 4 >= 4.0.1, PHP 5)

levenshtein — Calcula a distância Levenshtein entre duas strings

Descrição

int levenshtein ( string $str1 , string $str2 )
int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )
int levenshtein ( string $str1 , string $str2 , function $cost )

Retorna a Levenshtein-Distance entre duas strings argumentos ou -1, se nenhuma das strings argumentos é mais longa que o o limite de 255 caracteres (255 seria mais do que o bastante para o nome ou comparação de dicionário, e ninguém sério estaria fazendo análises genéticas com PHP).

A distância Levenshtein é definida como o número mínimo de caracteres que você tem para substituir, inserir ou apagar para transformar str1 dentro de str2 . A complexidade do algoritmo é O(m*n), onde n e m são o comprimento da str1 e str2 (rather good when compared to similar_text(), which is O(max(n,m)**3), but still expensive).

Na sua forma mais simples a função pegará apenas as duas strings como parâmetros e calculará apenas o número de operações de inserção, substituição e deletação necessárias para transformar str1 em str2 .

Uma segunda variante pegará três parâmetros adicionais que definem o custo das operações de inserção, substituição e deletação. Esta é a mais geral e adapatável do que a variante um, mas não tão eficiente.

A terceira variante (que ainda não é implementada) será a mais geral e adaptável, mas também a alternativa mais lenta. Ela chamará uma função de usuário fornecida que determinará o custo para cada possível operação.

A função de usuário fornecida(The user-supplied function) será chamada com os seguintes argumentos:

  • operation to apply: 'I', 'R' ou 'D'
  • actual character in string 1
  • actual character in string 2
  • position in string 1
  • position in string 2
  • remaining characters in string 1
  • remaining characters in string 2
The user-supplied function has to return a positive integer describing the cost for this particular operation, but it may decide to use only some of the supplied arguments.

The user-supplied function approach offers the possibility to take into account the relevance of and/or difference between certain symbols (characters) or even the context those symbols appear in to determine the cost of insert, replace and delete operations, but at the cost of losing all optimizations done regarding cpu register utilization and cache misses that have been worked into the other two variants.

Veja também soundex(), similar_text(), e metaphone().

Strings
PHP Manual