Determinando quão semelhante uma determinada string é a uma coleção de strings

10

Não tenho certeza se esta pergunta pertence aqui e peço desculpas se não. O que pretendo fazer é desenvolver uma maneira programática na qual eu possa determinar probabilisticamente se uma determinada string "pertence" a um pacote de strings. Por exemplo, se eu tiver um pacote de 10.000 nomes de cidades dos EUA e a sequência "Filadélfia", gostaria de obter uma medida quantitativa da probabilidade de "Filadélfia" ser um nome de cidade dos EUA com base nos nomes de cidades dos EUA que eu já conheço. Embora eu saiba que não vou conseguir separar nomes de cidades reais de nomes de cidades falsos nesse contexto, eu pelo menos esperaria ter seqüências de caracteres como "123,75" e "A rápida raposa vermelha saltou sobre os preguiçosos cães marrons" excluídas algum limiar.

Para começar, observei o Levenshtein Distance e dei uma olhada em como isso foi aplicado a problemas pelo menos um pouco semelhantes ao que estou tentando resolver. Uma aplicação interessante que encontrei foi a detecção de plágio, com um artigo descrevendo como a distância de Levenshtein foi usada com um algoritmo Smith-Waterman modificado para pontuar documentos com base na probabilidade de serem uma versão plagarizada de um determinado papel base. Minha pergunta é se alguém poderia me apontar na direção certa com outros algoritmos ou metodologias estabelecidos que possam me ajudar. Tenho a sensação de que isso pode ser um problema que alguém no passado tentou resolver, mas até agora meu Google-fu me falhou.

Andrew
fonte
Se você tiver exemplos positivos e negativos disponíveis, tente treinar um classificador. Para recursos, para começar, tentaria extrair algumas estatísticas simples, como as sugeridas por Yuval Filmus.
21412 Nick
Observe esta questão relacionada .
Raphael
Os nomes das cidades parecem ser um mau exemplo; eles estão por todo o lugar, especialmente nos EUA. Aqui, a pesquisa de tabela parece ser a maneira mais eficaz. O seu problema é mais geral?
Raphael

Respostas:

5

Algumas estatísticas melhores para se pensar são a análise do comprimento das palavras e do diagrama . Para o comprimento das palavras, você pode coletar estatísticas da distribuição do comprimento das palavras dos nomes das cidades e compará-las com o comprimento obtido. análise -gram analisa a distribuição das seqüências de letras no texto de amostra (digamos ). Ambas as abordagens podem ser combinadas.nnnn=2

Dadas as heurísticas, você pode usar a probabilidade de obter uma pontuação que (espero) seja maior para os dados da amostra do que para outros textos. Para determinar um limite razoável, você pode executar a validação cruzada. Escolha um conjunto de frases de exemplo que não sejam nomes de cidades. Divida os nomes das cidades em duas partes, uma parte grande (digamos 80%) e uma parte pequena (digamos 20%). Treine seu modelo na parte grande (ou seja, colete estatísticas na parte grande) e avalie-o na parte pequena e na amostra de frases ruins. Determine se existe um limite razoável que passe na maioria dos nomes de cidades, mas apenas uma pequena quantidade de frases ruins.

Yuval Filmus
fonte
Obrigado. Eu tinha começado a pesquisar no n-gram, mas não sabia se estava totalmente fora da base, então estou feliz que você tenha mencionado isso. O comprimento das palavras também parece interessante e algo em que eu não tinha pensado.
18713 Andrew Andrew
Você pode adicionar frequência de caracteres a isso. Em particular, isso deve se livrar de todas as coisas numerosas. Uma vantagem é que essas frequências são vetores de números que podem ser treinados / reconhecidos em vários modelos estatísticos.
Raphael
11
1 1n+1 1n