Diogo Luis Von Grafen Rubert
O USO DE FUNÇÕES DE SIMILARIDADE E DISTÂNCIA ENTRE
STRINGS ADAPTADAS AO PORTUGUÊS BRASILEIRO
Agosto de 2015
2
Roteiro de Apresentação Motivação; Recuperação de informações; Contrib Fuzzystrmatch; Algorimos Fonéticos e de Distância; Soundex; Metaphone;
3
Roteiro de Apresentação
Levenshtein; Fonemas; Adaptação para o Português; Testes; Métricas; Conclusões.
4
Motivação
Comunidade do PostgreSQL; Índice para Levenshtein; Função Soundex(); Contrib fuzzystrmach.
5
Motivação
Qual a relação com Inteligência Artificial?
Porque não é uma função nativa? Qual função é a melhor?
6
Recuperação de Informações
Pode ser ineficiente por meio dos métodos tradicionais;
select * from pessoas p where p.nome = ‘nome’;
select * from pessoas p where p.nome LIKE ‘nome%’;
select * from pessoas p where upper(p.nome) LIKE upper(‘nome%’);
7
Recuperação de Informações
Falha humana:
CAMPINAS – CSMPINAS JOÃO – JOAO THIAGO – TIAGO JOÃO – JOAO
8
Recuperação de Informações
O erro humano não deve impedir que uma busca seja bem sucedida;
Inconsistências no banco de dados também não devem impedir;
As funções de similaridade tem inúmeras aplicabilidades;
9
Recuperação de Informações
Exemplos de aplicabilidades: Segurança; Hospitais; Universidades; ...
10
Recuperação de Informações
Como resolver este problema?
11
Fuzzystrmatch O módulo fuzzystrmatch fornece várias
funções para determinar as semelhanças e distância entre strings.
Disponibiliza as funções: Soundex; Difference; Metaphone; Dmetaphone; Levenshtein.
12
Fuzzystrmatch O módulo fuzzystrmatch fornece várias
funções para determinar as semelhanças e distância entre strings.
Disponibiliza as funções: Soundex; Difference; Metaphone; Dmetaphone; Levenshtein.
13
Algoritmos Fonéticos
Algoritmos fonéticos são aqueles baseados na forma como as palavras são pronunciadas; Luiz, Luis, Luís; Tiago, Thiago, Thyago; Vanderson, Wanderson, Wandersom; Marcelo, Marcello.
14
Algoritmos de Distância
Algoritmos de distância entre strings são baseados em caracteres; Luid, Lxís; Tihgo, Txiago; Mrcelo, Marcllo.
Ambos são baseados em lógica fuzzy.
15
Algoritmos Fonéticos e de Distância
Tem como objetivo tratar problemas de erros de ortografia ou de digitação dos dados;
A intenção destes métodos é ir além da busca exata, aquela que utiliza operadores relacionais. Igualdade (=); Like.
16
Soundex
Foi criado por Robert C. Russell e Margaret K. Odell em 1918;
A intenção era ordenar o nome das pessoas pela forma como eram pronunciadas e não em ordem alfabética.
17
Soundex Colocar em ordem alfabética:
João Carlos; João Alberto; João Albino; João Antônio; João Fernando; João Francisco; Joana.
18
Soundex
É formado pela letra inicial mais três números obtidos a partir de uma tabela;
Letras duplicadas ou que possuem o mesmo valor na tabela, devem ser tradadas como uma só;
As vogais são ignoradas.
19
Soundex
Letras Valor
A, E,, I, O, U, H, W, Y 0
B, P, F, V 1
C, S, G, J, K, Q, X, Z 2
D, T 3
L 4
M, N 5
R 6
20
SoundexNomes Código Soundex
Diogo D200
Christopher, Christofer, Cristopher C623
Russell, Rusel R240
Wellington, Wellingtom, Welington W452
select * from pessoas p where soundex(p.nome) = soundex(‘nome’);
21
Soundex Nomes pronunciados de forma
semelhante, possuem o mesmo código;
Uma das deficiências é não conseguir tratar a combinação de algumas letras que formam sons diferentes (Cléber e Kléber): Neste caso, são representadas por C416
e K416, respectivamente.
22
Problema E quando a mesma letra tem um som
diferente?
23
Metaphone Foi escrito por Lawrence Philips em 1990
com o objetivo de suprir as deficiências do Soundex;
A ideia do Metaphone é identificar a posição onde a letra está inserida, para assim definir a sua melhor representação;
Não são consideradas apenas consoantes para definir uma representação fonética;
O autor também desenvolveu os métodos Double Metaphone e Metaphone 3.
24
Metaphone
Nomes Códigos MetaphoneDiogo TK
Benjamin, Bengeamin BNJMN
Franklin, Franqulin FRNKLN
Willian, Wilian WLM
select * from pessoas p where metaphone(p.nome) = metaphone (‘nome’);
25
Metaphone Palavras que soam de maneira
semelhante serão representadas da mesma forma;
Faz o tratamento contextual dos caracteres;
Não existe um tamanho limite para a representação fonética da palavra, enquanto no Soundex o limite é de apenas quatro caracteres.
26
Problema
E se ocorreram erros de digitação que mudaram a forma que uma
palavra é pronunciada?
27
Problema Qual a distância entre as palavras a
seguir?
Diogo – Diego Diogo – Tiago Diogo – Luís
28
Levenshtein O conceito da distância de
Levenshtein foi escrito em 1965 pelo matemático Vladimir I. Levenshtein e baseado na distância de Hamming;
O princípio de Levenshtein é definir a distância entre duas palavras com base no número de operações necessárias para torná-las iguais;
29
Levenshtein
Operações possíveis: inserção, exclusão ou substituição ;
Wagner e Fisher (1974) desenvolveram um algoritmo que reduziu a complexidade do cálculo para m x n.
30
Levenshtein
String1 String2 DistânciaDiogo Diogo 0
Diogo Diego 1
Diogo Tiago 2
Diogo Luis 5
select * from pessoas p where levenshtein(p.nome, ‘nome’) <= 1;
31
Levenshtein
Palavras semelhantes têm uma distância menor;
O algoritmo pode ser lento para comparar strings muito longas, pois a matriz que precisa ser criada é diretamente proporcional ao tamanho de cada string.
32
Problema
As funções fonéticas da contrib fuzzystrmatch não são usuais
para idiomas diferentes do inglês.
33
Fonemas O ser humano é dotado do aparelho
fonador, responsável por produzir a fala; O estudo dos sons que emitimos é
denominado fonologia; Como cada linguagem possui sons
diferentes, o estudo das particularidades chama-se fonética;
Na fonética, pode-se dizer que a unidade que distingue um som de outro é o fonema.
34
Fonemas
35
Adaptação do Soundex A tabela de códigos Soundex criada por
Russell foi baseada na classificação do ponto de articulação dos fonemas da língua inglesa;
Para adaptar o Soundex para o português brasileiro, a proposta é mudar o valor da tabela de códigos baseado na classificação fonética língua portuguesa;
Consoantes que juntas formam um só fonema, como “CH”, “LH” e “NH”, devem ser tratadas.
36
Adaptação do Soundex
Letra(s) Valor Pontos de Articulação
A, E, I, O, U, H, W, Y 0 -
P, B, M 1 Bilabiais
F, V 2 Labiodentais
T, D, N 3 Linguodentais
L, R 4 Línguo-Alveolares
S, Z 5 Línguo-Alveolares Convexas
J, DI, GI, TI, CH, LH, NH 6 Línguo-Palatais
K, C, G, Q 7 Velares
X 8 -
37
Adaptação do Metaphone
Exige conhecimento de fonologia e língua portuguesa;
Metaphone para inglês: 22 regras;
Metaphone para português: 49 regras;
38
Adaptação do Metaphone Carlos C. Jordão e João Luís G. Rosa
(2012) escreveram um artigo sobre a importância da fonética na busca e correção de informações textuais;
Neste artigo, apresentaram uma proposta de adaptação para o português brasileiro, denominado Metaphone-pt_BR;
Alguns sons que não existem na língua inglesa foram representados pelos números 1, 2 e 3;
39
Adaptação do Metaphone
Licença BSD; Link: http
://sourceforge.net/projects/metaphoneptbr/
40
Testes
Algoritmos fonéticos podem ser pré-processados;
São preferíveis em relação as buscas por distância;
Os melhores resultados são obtidos com métodos híbridos.
41
Métricas Utilizadas Conforme Silberschatz (2006), para
medir a eficácia de funções que recuperam informações, podem ser aplicadas medidas de precisão e de revocação. Precisão; Revocação ou Rechamada; Medida F Balanceada; Tempo.
42
Métricas Utilizadas Precisão: deve medir a taxa de acerto da função,
isto é, quantos registros foram retornados corretamente em relação a todos os registros retornados;
Revocação: deve medir a taxa de registros relevantes retornados, ou seja, quantos registros foram retornados corretamente em relação ao total de registros que a função deveria de fato retornar;
Medida F Balanceada: é a média harmônica ponderada da precisão e da revocação. Utilizada para medir a relação entre as duas métricas utilizadas;
43
Testes Realizados
Foram realizados a partir da coleta de algumas amostras de cada base de dados;
Foram feitos os seguintes experimentos: Dado inicial correto; Dado inicial foneticamente
correto; Dado Inicial foneticamente
incorreto.
44
Conclusões Quando o dado inicial está correto,
todos os métodos atingiram 100% no quesito revocação;
No quesito precisão, as funções fonéticas demonstraram ser bastante eficientes quando ocorrem erros de digitação;
A função br_metaphone se sobressai em relação as demais. Os dados retornados por esta função foram bastante precisos e chegaram a 99,1% de precisão.
45
Conclusões Quanto a performance, comprovou-se a
função levenshtein seria a menos performática, afinal não pode ser pré-processada;
A função br_soundex foi superior as demais em todas as consultas no que refere-se a performance;
Contudo, em relação performance, pode-se afirmar que em pequenas bases de dados, o tempo foi irrelevante;
Em grandes bases de dados este quesito pode ganhar maior importância.
46
Conclusões As funções de similaridade
mostraram ser uma alternativa interessante para suprir as limitações dos operadores lógicos.
O uso destas técnicas tem aplicabilidades em inúmeros tipos de sistema.
Os métodos estudados são eficientes com palavras do dicionário.
47
Problemas e Oportunidades
Comparar a utilização de outras técnicas de detecção de similaridade entre strings: Baseadas em caracteres; Baseadas em token; Baseadas em fonética; Baseadas em trigramas.
48
Dúvidas
Diogo Luis Von Grafen Rubert