pesquisa e testes
testamos vários algoritmos para comparar strings e selecionamos aquele que melhor se adequaria à nossa necessidade.
Nós comparação de Seqüência de caracteres de Uma Seqüência de caracteres e B para ter métricas sobre os diferentes algoritmos.
as regras para similaridade de string podem diferir de caso para caso. Se você quiser considerar “nicho” e “chien” semelhantes, você usaria um algoritmo de similaridade de string que detecta anagramas. Não no nosso caso. Um aplicativo chamado “nicho” e outro chamado “chien” provavelmente serão dois aplicativos completamente diferentes.
após algum brainstorming e pesquisa, criamos alguns métodos de algoritmo que ajudariam nosso caso. O algoritmo de cosseno provou ser irrelevante para nós, pois, por exemplo, não parece levar em conta a ordem das letras, O que leva a um índice de 1 (string semelhante) em um anagrama (“nicho” e “chien”).
aqui está o que notamos:
algoritmo Levenshtein
a distância Levenshtein é o número mínimo de edições de caractere único necessárias para alterar uma palavra para a outra, portanto, o resultado é um inteiro positivo, sensível ao comprimento da string . O que torna mais difícil desenhar padrão.
Por exemplo,
- a distância de Levenshtein entre “foo” e “bar” é 3
- a distância de Levenshtein entre as “belezas” e o “belo”, é também 3
- Para nós, seres humanos, as “belezas”/”belo par” é muito mais semelhantes do que os “foo”/”barra” par. Mas a distância de Levenshtein é a mesma.
a métrica que estamos usando aqui é o inverso da distância Levenshtein (1 / levenshtein_distance), então o resultado é uma porcentagem e é mais facilmente lido por nós. Mas o problema mencionado acima permaneceu o mesmo.
onde 1 é o resultado da comparação de strings idênticas,” ShazamIphone “e” ShazamAndroid ” têm uma semelhança de 0,167. “chien” e “nicho” têm uma semelhança de 0,25.
Portanto, do ponto de vista do algoritmo Levenshtein, Chien / Niche são mais semelhantes do que “ShazamIphone”/”ShazamAndroid” porque são necessárias menos edições para ir de “chien” a “nicho”, do que ir de “ShazamIphone” a “ShazamAndroid”.
comparação de Trigramas
um algoritmo de trigramas é um caso de n-gram, uma sequência contígua de n (Três, neste caso) itens de uma determinada amostra. No nosso caso, um nome de aplicativo é uma amostra e um caractere é um item.
então a sequência “martha” tem 4 trigramas { mar art rth tha}.
podemos usar o método Trigram para comparar duas strings.
Tomando por exemplo “marta” e a mesma palavra com erro ortográfico, “marhta”, e podemos calcular os trigramas:
Trigramas “marta”: { mar de arte rth tha }
Trigramas “marhta”: { mar arh lht hta }
Para medir a similaridade divide-se o número de correspondência trigramas em ambas as seqüências de caracteres: 1 { mar } pelo número de trigramas exclusivos: 7 { mar de arte rth tha arh lht hta }
The result is 1/7 = 14%
Para equilibrar a desvantagem do exterior caracteres (de certa forma para reforçar a similaridade de seqüências de caracteres começando e terminando com a mesma trigramas), vamos preencher a seqüência de caracteres com espaços em branco em ambos os lados, resultando em caso de mais três trigramas “_ma”, “ha_” e “ta_”.
Trigramas ” marta “: { _ma mar de arte rth tha ha_ }
Trigramas ” marhta “: { _ma mar arh lht hta ta_ }
Tendo feito isso, o número de correspondência trigramas é de até: 2 { _ma mar }
O número de todos os trigramas exclusivos: 9 { _ma mar de arte rth tha arh lht hta ha_ }
The result is now 2/9 = 22%
Usando este método para comparar “o Twitter v1” e “Twitter v2”, temos:
O número de correspondência trigramas: 7 { _tw twi sagacidade itt tte ter er_ }
O número de todos os trigramas exclusivos: 11 { tw twi sagacidade itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
O limite do Trigrama método para comparar seqüências de caracteres é que cadeias curtas com um (ou dois..) trigramas diferentes tendem a produzir uma semelhança menor do que os longos.
é assim que obtemos um 0.2 semelhança entre” ShazamAndroid “e” ShazamIphone”, pois eles têm trigramas mais diferentes.
o número de trigramas correspondentes é: 5 { _sh Sha haz Aza zam}
O número de todos os trigramas únicos: 20
como há uma forte dependência com o comprimento da string, não produz uma boa comparação para nós.
algoritmo jaro-Winkler
“Em Ciência da computação e Estatística, a distância jaro-Winkler é uma métrica de string para medir a distância de edição entre duas sequências.Informalmente, a distância Jaro entre duas palavras é o número mínimo de transposições de caractere único necessárias para mudar uma palavra para a outra.
a distância jaro-Winkler usa uma escala de prefixo que dá classificações mais favoráveis para strings que correspondem desde o início para um comprimento de prefixo definido”
fonte: Wikipedia.
dar “mais importância” a palavras com prefixos idênticos fez com que a distância Jaro-Winkler parecesse muito interessante para o nosso caso de uso.
começando do início com a fórmula de distância Jaro, aqui como funciona. Não entre em pânico, temos de ir passo a passo:
O Jaro Distância entre duas seqüências s1 e s2 é definida por:
dj é o Jaro distância
m é o número de caracteres correspondentes (personagens que aparecem em s1 e em s2)
t é a metade do número de transposições (compare-se o i-ésimo caractere de s1 e o i-ésimo caractere do s2 dividido por 2)
|s1| é o comprimento da primeira seqüência de caracteres
|s2| é o comprimento da segunda string
Com um exemplo. Vamos pegar “martha ” e”marhta”.
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
apenas substituindo números é a fórmula, obtemos:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
agora sabemos qual é a distância Jaro, vamos pular para a distância jaro-Winkler.
a similaridade Jaro-Winkler usa uma escala de prefixo p que dá classificações mais favoráveis para strings que correspondem desde o início para um comprimento de prefixo definido l.
p é um fator de escala constante para o quanto a pontuação é ajustada para cima por ter prefixos comuns. O valor padrão para essa constante no trabalho de Winkler é p=0,1.
l é o comprimento do prefixo comum no início da string (até um máximo de 4 caracteres).
Então, de volta para a “marta”/ “marhta” exemplo, vamos tomar um prefixo de comprimento l = 3 (que se refere ao “mar”). Nós chegamos a:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
usando a fórmula JaroWinkler, Vamos da distância Jaro a 94% de semelhança com 96%.
no nosso caso, a maioria dos aplicativos semelhantes começa com o mesmo prefixo (“twitter v1” vs “twitter v2” ou “ShazamIphone” vs “ShazamAndroid” etc. Veja a tabela de testes de algoritmos acima). Portanto, é um critério importante a ser levado em consideração.
