Adversário misterioso: empréstimos confusos

Empréstimo ilegal é uma hidra de várias cabeças, um inimigo que muda constantemente de rosto. Nossos melhores investigadores particulares estão prontos para se apegar a qualquer crime cometido por esse inimigo. No entanto, o inimigo não dorme, ele é astuto e traiçoeiro: obviamente, substituindo uma coisa, ele incrivelmente habilmente varre traços em outras. Às vezes, ele consegue pegar em flagrante com a ajuda de nosso funcionário mais ágil - o sufixo Massiv . Às vezes, o inimigo hesita, e a busca meticulosa, mas sem pressa, de Paráfrase consegue calcular sua localização. Mas o mal é insidioso, e precisamos constantemente de novas forças para combatê-lo .

Hoje falaremos sobre o nosso novo detetive para fins especiais chamado Fuzzy Search , bem como seu primeiro encontro com empréstimos difusos.

Com sua agência de detetives Antiplagiarism , prepare-se para o Caso Oponente Misterioso

Scene

Ao verificar a área (documento), o Anti-Plágio verifica se há alguma ligação sobre um possível crime na área. As testemunhas oculares que nos sinalizarão sobre o crime são o Índice Shingles .

"Uma telha é um pedaço de texto com poucas palavras." Cada uma dessas peças é dividida em hash e os documentos com telhas com os mesmos hashes do documento que está sendo verificado são pesquisados ​​no índice.

Uma testemunha ocular, vendo uma coincidência no hash de duas telhas, nos chama com uma mensagem sobre o crime. Infelizmente, o índice de telhas não pode ser punido por uma chamada falsa, é imune a sanções, e é por isso que existem muitas chamadas. A agência determina os documentos com o maior acúmulo de chamadas - a cena de um crime em potencial.

Primeira pista

Agora você é um detetive, filho.
A partir de agora você está proibido de acreditar em coincidências.

O detetive Fuzzy Search chegou à cena do crime. Criminosos grandes o suficiente não passam despercebidos, porque quanto maior a escala do crime, maior a probabilidade de deixar uma pista. Para a Pesquisa difusa, esses leads são correspondências curtas de comprimento fixo. Parece que nosso detetive está perdendo uma grande parte dos traços de criminosos habilmente varridos, mas apenas 5% dos atacantes não deixam essa pista. É importante não perder criminosos, para que o detetive vasculhe rapidamente a área usando uma técnica especial para detectar partidas.

O diário do detetive sobre o método de trabalho. Primeira etapa

Usaremos dois recursos da tarefa:

1. Estamos interessados ​​em duplicatas claras de comprimento fixo.
2. Em um bom documento, a mesma telha não é duplicada muitas vezes.

A segunda condição é necessária para limitar o número de duplicatas limpas encontradas. De fato, um single que ocorre 1000 vezes no documento e na fonte dará 1.000.000 de pares de correspondências. Tais telhas frequentemente repetidas só podem ser vistas em documentos não limpos com tentativas de rastreamento.

Um documento limpo de rastreamentos é apresentado como uma sequência de palavras. Trazemos as palavras para a forma normal das palavras e depois as misturamos. Temos uma sequência de números inteiros (no gif - uma sequência de letras). Todas as telhas dessa sequência são divididas em hash e inseridas na tabela de hash com o valor da posição do início da substring. Em seguida, para cada telha no documento candidato, são encontradas correspondências na tabela de hash. Isso cria duplicatas claras de comprimento fixo. Os testes mostram aceleração tripla ao usar o novo método em comparação com a matriz de sufixos.

Nós calculamos o criminoso

- Há algum outro ponto que você me aconselharia a prestar atenção?
"O comportamento estranho do cachorro na noite do crime."
Cães? Mas ela não se comportou de forma alguma!
"Isso é estranho", disse Holmes.

_{© Arthur Conan-Doyle, “Silver” (da série “Notes on Sherlock Holmes”)}

Portanto, a Fuzzy Search encontrou várias pistas para identificar criminosos. Nosso herói usa suas habilidades dedutivas ao máximo, para, aos poucos, restaurar gradualmente a imagem do criminoso, de acordo com as pistas encontradas. O detetive está gradualmente expandindo a imagem do que está acontecendo, complementando-a com novos detalhes, descobrindo cada vez mais evidências até que essa imagem finalmente se torne completa. Às vezes, nosso detetive é trazido, e ele precisa ser baixado do céu para a terra e convencido de que precisamos da identidade do criminoso, e não da biografia de seu primo. A Pesquisa difusa resmunga, mas humildemente restringe a imagem na escala desejada.

O diário do detetive sobre o método de trabalho. Segunda etapa

_{Fonte da imagem: pixabay.com}

O segundo estágio distribui duplicatas à esquerda e à direita no documento. A distribuição vem dos "centros" - encontrados duplicados claros. Para comparar os sufixos, usamos a distância de Levenshtein - o número mínimo de exclusões / substituições / inserções de palavras necessárias para trazer uma linha para outra. A distância pode ser calculada dinamicamente para sufixos duplicados usando o algoritmo de Wagner-Fisher , com base na determinação recursiva da distância de Levenshtein. No entanto, esse algoritmo é quadrático em complexidade e não permite controlar a proporção de erros. Outro problema é a definição exata dos limites das duplicatas. Para resolver esses problemas, usamos vários procedimentos simples, mas eficazes.

Nesta etapa, propõe-se primeiro o preenchimento sequencial da matriz de distância de Levenshtein para sufixos duplicados nebulosos (depois, da mesma forma, para prefixos). Como verificamos sufixos em busca de “similaridade”, estamos interessados ​​apenas em valores próximos à diagonal dessa matriz (a distância de Levenshtein é maior ou igual à diferença no comprimento das linhas). Isso permite complexidade linear. Depois de definir a distância máxima permitida de Levenshtein, preencheremos a tabela até encontrarmos uma coluna com valores maiores que os permitidos. Essa coluna indica que nossa duplicata difusa terminou recentemente e as palavras quase coincidiram completamente. Depois de salvar o ideal anterior para cada célula preenchida, descemos da célula com uma penalidade mínima na coluna crítica até encontrarmos várias correspondências, após as quais o erro começou a aumentar acentuadamente. Esses serão os limites da duplicação difusa encontrada.

Além disso, para que os erros não se acumulem, é introduzido um procedimento que redefine o número de erros, iniciando a propagação novamente se tropeçarmos em uma "ilha" por sucessivas coincidências.

Gangue de criminosos

- Amanhã planejamos nos reunir com colegas!
- Em um grande colega de classe?
- o que?

_{© Bashorg}

A busca difusa permaneceu uma tarefa simples: unir os criminosos presos no mesmo lugar em quadrilhas, justificar os suspeitos inocentes e coletar os resultados juntos.

_{Fonte da imagem: pixabay.com}

Colar duplicados resolve imediatamente três problemas. Em primeiro lugar, o segundo estágio da “distribuição de duplicados” absorve modificações de palavras e frases, mas não frases inteiras. Se você aumentar a "capacidade de espalhamento" do algoritmo, ele começará a se espalhar por coincidências encontradas a uma distância muito grande e os limites das duplicatas serão determinados de maneira pior. Portanto, perdemos a precisão tão importante para nós, que uma pesquisa clara teve.

Em segundo lugar, o segundo estágio não reconhece a permutação de duas duplicatas. Gostaria que a permutação das duas frases em alguns lugares formasse uma frase próxima ao original, mas para uma linha de caracteres únicos, a permutação do prefixo e sufixo em alguns lugares leva à linha o mais longe possível do original (na métrica de Levenshtein). Acontece que o segundo estágio, ao reorganizar as frases, encontra duas duplicatas localizadas próximas umas das outras que você deseja mesclar em uma.

E a terceira razão é Granularidade, ou Granularidade. Granularidade é uma métrica que determina o número médio de duplicatas encontradas em um empréstimo verdadeiro que encontramos. Em outras palavras, a granularidade mostra quão bem encontramos todo o empréstimo, em vez das poucas partes que o cobrem. A definição formal de granularidade, bem como a definição de precisão e integridade micro-médias, podem ser encontradas no artigo “Uma estrutura de avaliação para detecção de plágio” .

Gifka mostra que, às vezes, duas duplicatas podem ser coladas somente depois que uma delas adere à terceira duplicada. Portanto, apenas uma passagem da esquerda para a direita no documento não funciona para concluir a colagem.

Treinamento para iniciantes

O detetive precisava se adaptar às características de nossa cidade, adaptar-se ao terreno, passear pelas ruas imperceptíveis e conhecer melhor seus habitantes. Para isso, um iniciante faz um curso de treinamento especial no qual estuda situações semelhantes em um campo de treinamento. Na prática, o detetive estuda as pistas, a dedução e a construção de laços sociais para a captura mais eficaz de criminosos.

O modelo paramétrico precisava ser otimizado. Para determinar os parâmetros ideais do modelo, foi utilizada a amostra PlagEvalRus .

A amostra é dividida em 4 coleções:

• Generated_Copypast (4250 pares) - empréstimos gerados literalmente
• Generated_Paraphrased (4250 pares) - empréstimos com modificação fraca e média gerados pela máquina usando o ruído das passagens originais (substituições / exclusões / inserções arbitrárias)
• Parafraseado manualmente (713 pares) Textos escritos à mão com vários tipos de empréstimos, principalmente empréstimos fracos e com modificações médias (substituídos por não mais que 30% das palavras na duplicata)
• Parafraseado manualmente 2 (198 pares) Textos manuscritos com empréstimos médios e altamente modificados (mais de 30% de palavras)

A busca pelos parâmetros ótimos do modelo foi realizada pelo método de descida multi-partida. Maximizado $$$F_ \ beta$medir com $$$\ beta ^ 2 = \ frac {1} {4}$(ênfase na precisão). Aqui estão os parâmetros ótimos mais significativos.

Histórico de casos

O período de teste da nossa Pesquisa difusa chegou ao fim. Vamos comparar sua produtividade com a de outro detetive, o Suffix Array. O curso de treinamento Fuzzy Search ocorreu no programa Manually_Paraphrased.

No campo, o recém-chegado mostrou superioridade significativa na proporção de casos resolvidos. A velocidade de seu trabalho também não pode deixar de se alegrar. Nossa agência não tinha um funcionário tão valioso.

Comparando a qualidade do modelo com a matriz de sufixos, notamos uma melhora significativa na granularidade, bem como uma melhor detecção de empréstimos médios e altamente modificados.

Testando em documentos com até 10 ⁷ palavras, verificamos a linearidade de ambos os algoritmos. No processador i5-4460, o programa processa um par de "fontes de documentos" com um milhão de palavras em menos de um segundo.

Tendo gerado textos com um grande número de empréstimos, estamos convencidos de que a pesquisa difusa (linha azul) não é mais lenta que a matriz de sufixos (linha vermelha). Por outro lado, uma matriz de sufixos sofre em documentos grandes de muitas duplicatas. Comparamos o desempenho com um comprimento duplicado mínimo de 5 palavras. Porém, para uma cobertura suficiente de empréstimos, usamos uma pesquisa clara com um comprimento mínimo duplicado de três palavras, o que em documentos gigantescos leva a uma queda significativa na produtividade (linha laranja). Vale a pena notar que documentos comuns contêm menos empréstimos e, na prática, esse efeito é muito menos pronunciado. Mas esse experimento nos permite entender a expansão da aplicabilidade dos modelos com uma nova pesquisa difusa.

Exemplos:

Pode-se observar que o algoritmo, apesar da pequena complexidade computacional, lida com a detecção de substituições / exclusões / inserções, e o terceiro passo permite detectar empréstimos com a permutação de frases e suas partes.

Epílogo

A Pesquisa Difusa trabalha em equipe com nossas outras ferramentas: Pesquisa rápida para documentos candidatos, Extração de formatação de documentos, Captura em larga escala de tentativas de desvio. Este comando permite encontrar rapidamente plágio potencial. A Pesquisa Difusa criou raízes nessa equipe e executa suas funções de pesquisa de maneira mais qualitativa e, mais importante, mais rápida do que a Matriz de Sufixo. Nossa agência lidará ainda melhor com suas tarefas, e autores inescrupulosos encontrarão novos problemas ao usar texto não original .

Crie com sua própria mente!