String metric - String metric
Em matemática e ciência da computação , uma métrica de string (também conhecida como métrica de similaridade de string ou função de distância de string ) é uma métrica que mede a distância ("similaridade inversa") entre duas strings de texto para correspondência ou comparação aproximada de string e na pesquisa de string difusa . Um requisito para uma métrica de string (por exemplo, em contraste com a correspondência de string ) é o cumprimento da desigualdade do triângulo . Por exemplo, as cadeias de caracteres "Sam" e "Samuel" podem ser consideradas próximas. Uma métrica de string fornece um número que indica uma indicação de distância específica do algoritmo.
A métrica de cordas mais conhecida é uma rudimentar chamada distância de Levenshtein (também conhecida como distância de edição). Ele opera entre duas strings de entrada, retornando um número equivalente ao número de substituições e exclusões necessárias para transformar uma string de entrada em outra. Métricas de string simplistas, como distância de Levenshtein, foram expandidas para incluir métodos fonéticos, de token , gramaticais e baseados em caracteres de comparações estatísticas.
As métricas de string são amplamente utilizadas na integração de informações e atualmente são utilizadas em áreas como detecção de fraude , análise de impressão digital , detecção de plágio , fusão de ontologia , análise de DNA , análise de RNA, análise de imagem , aprendizado de máquina baseado em evidências , deduplicação de dados de banco de dados , mineração de dados , incremental pesquisa , integração de dados , detecção de malware e integração de conhecimento semântico .
Lista de métricas de string
- Distância de Levenshtein , ou distância de edição de generalização
- Distância Damerau-Levenshtein
- Coeficiente de Sørensen-Dice
- Distância do bloco ou distância L1 ou distância do bloco da cidade
- Distância de Hamming
- Distância Jaro – Winkler
- Coeficiente de correspondência simples (SMC)
- Similaridade de Jaccard ou coeficiente de Jaccard ou coeficiente de Tanimoto
- Índice Tversky
- Coeficiente de sobreposição
- Distância variacional
- Distância Hellinger ou distância Bhattacharyya
- Raio da informação ( divergência de Jensen-Shannon )
- Divergência de enviesamento
- Probabilidade de confusão
- Tau metric , uma aproximação da divergência Kullback-Leibler
- Métrica Fellegi e Sunters (SFS)
- Correspondências máximas
- Distância baseada em gramática
- TFIDF distância métrica
Exemplos de medidas de string selecionadas
| Nome | Exemplo |
|---|---|
| Distância de Hamming | " ka rol in " e " ka thr in " são 3. |
| Distância de Levenshtein e distância Damerau – Levenshtein |
k itt e n e s itt i n g têm uma distância de 3.
|
| Distância Jaro – Winkler | JaroWinklerDist ("MARTHA", "MARHTA") =
|
| Caracteres k mais frequentes | MostFreqKeySimilarity (' r e s e a r ch', 's ee king', 2) = 2 |
Referências
links externos
- https://web.archive.org/web/20070304092115/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html#qgram Uma visão geral bastante completa Índice de arquivo na máquina Wayback
- Biblioteca de código aberto da Carnegie Mellon University
- StringMetric projeta uma biblioteca Scala de métricas de string e algoritmos fonéticos
- Natural project uma biblioteca de processamento de linguagem natural JavaScript que inclui implementações de métricas de string populares