como disse na outra tread, me indicaram uma ferramenta de um alemão que faz as comparações entre tabelas de ruas de cadastros (ex: CNEFE) contra o OSM. É aqui: http://regio-osm.de/listofstreets/hierarchy . Tem pro Brasil inclusive. Acho que á similar ao que você está propondo, apensar de que não sei alemão para saber se as estatísticas são exatamente as mesmas.
Heh estou querendo dar uma olhada em detalhe nas suas idéias desde ontem (achei elas muito interessantes! mas essa semana só deu pra ler por altos por enquanto). Olhei por altos também o site (entendo um pouco de alemão - e pro resto uso dicionários :P) mas não descobri exatamente qual o método de comparação. Acho (mas ainda não tenho certeza) que é uma comparação caractere a caractere (nomes exatos entre dois cadastros).
Além disso, só tem a região sul do Brasil lá. Talvez estejam usando para fazer algum tipo de teste.
Acho que são todas idéias bem parecidas, relacionadas e que podem se beneficiar/se inspirar mutuamente.
Fernando Trebien,
Muito legal esse batimento de nomes de ruas usando Levenshtein! Fiz uma pequena modificação para evitar a chamada da distância de Levenshtein quando a diferença dos tamanhos dos nomes for maior que a menor já encontrada. Economizando essa chamada o tempo cai de 50 para 34s em Python, no meu notebook.
Anexei uma versão em Lua caso alguém tenha interesse. É uma linguagem brasileira e em média duas vezes mais rápida que Python 3 (http://benchmarksgame.alioth.debian.org/u64/benchmark.php?test=all&lang=lua&lang2=python3&data=u64). Se usarmos LuaJIT podemos ter ainda um bom ganho adicional.
Essa versão inclui a função levenshtein em Lua mesmo, caso uma lib externa em C não esteja disponível, mas fica um pouco mais lenta, roda em cerca de 45s. Fiz um binding da Levenshtein em C para Lua (x86_64, Linux) para ficar equivalente à versão em Python e nesse caso o tempo cai para 24 a 27s dependendo de pequeno ajuste no código (um fica melhor para Levenshtein em Lua e outro para Levenshtein em C). Tempos medidos com LuaJIT. Se houver interesse posso disponibilizar o binding da Levenshtein.
O parser CSV também está em Lua mas esse altera pouco o tempo.
Abraços,
– Fidelis
local abs, byte, gsub, len, min, sub =
math.abs, string.byte, string.gsub, string.len, math.min, string.sub
-- tenta usar módulo Levenshtein em C
local erro, levenshtein = pcall(require, 'levenshtein')
-- se não encontrar a lib levenshtein.so, usa a função em Lua abaixo
if not erro then
io.write('Usando Levenshtein em Lua\n')
-- Função distância de Levenshtein portada para Lua a partir de exemplo em C no Wikilivros
-- http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
levenshtein = function(s1, s2)
local s1len, s2len, x, y, lastdiag, olddiag
local s1len = len(s1)
local s2len = len(s2)
local column = {}
for y=1, s1len do
column[y] = y
end
for x=1, s2len do
column[0] = x
lastdiag = x-1
for y=1, s1len do
olddiag = column[y]
column[y] = min(column[y] + 1, column[y-1] + 1, lastdiag + (byte(s1, y) == byte(s2, x) and 0 or 1))
lastdiag = olddiag
end
end
return column[s1len]
end
else
io.write('Usando Levenshtein em C\n')
levenshtein = levenshtein.distance
end
-- parser CSV específico em Lua
local function csv(linha)
linha = gsub(linha, '""', '"')
local a, b, c = linha:match('^(.-)\t(.-)\t(.+)')
if sub(c, 1, 1) == '"' and sub(c, -1, -1) == '"' then
c = sub(c, 2, -2)
end
if sub(a, 1, 1) == '"' and sub(a, -1, -1) == '"' then
a = sub(a, 2, -2)
end
return a, b, c
end
local filtro_cidades = false
local cidades = {[4314902] = true}
local arq_saida = 'comparacao_ruas_osm_cnefe_lua.txt'
local ruas_cidade_cnefe = {}
local comparacao = {}
local duplicata = {}
for linha in io.lines('municipio_cep_RUA_CNEFE.txt') do
local cidade, _, rua = csv(linha)
if not ruas_cidade_cnefe[cidade] then
ruas_cidade_cnefe[cidade] = {}
end
ruas_cidade_cnefe[cidade][rua] = true
end
io.write 'Comparando...\n'
for linha in io.lines('municipio_rua_RUA_OSM.txt') do
local cidade, _, rua_osm = csv(linha)
if not filtro_cidades or cidades[cidade] then
local menor_distancia = 100000
local opcoes_cnefe = {}
local duplicata = {}
for rua_cnefe in pairs(ruas_cidade_cnefe[cidade]) do
local distancia = len(rua_cnefe) - len(rua_osm)
distancia = abs(distancia)
if distancia <= menor_distancia then
distancia = levenshtein(rua_osm, rua_cnefe)
if distancia < menor_distancia then
menor_distancia = distancia
opcoes_cnefe = {rua_cnefe}
elseif distancia == menor_distancia then
if not duplicata[rua_cnefe] then
opcoes_cnefe[#opcoes_cnefe+1] = rua_cnefe
duplicata[rua_cnefe] = true
end
end
end
end
if menor_distancia > 0 then
table.sort(opcoes_cnefe)
comparacao[#comparacao+1] = {cidade, menor_distancia, #opcoes_cnefe, rua_osm, opcoes_cnefe}
io.write('!')
else
io.write('.')
end
end
end
io.write('\n')
local function fsort(a, b)
if a[1] < b[1] then
return true
elseif a[1] == b[1] then
if a[2] < b[2] then
return true
elseif a[2] == b[2] then
if a[3] < b[3] then
return true
elseif a[3] == b[3] then
return a[4] < b[4]
end
end
end
return false
end
table.sort(comparacao, fsort)
comparacao_file = io.open(arq_saida, 'w')
for _, item in ipairs(comparacao) do
comparacao_file:write(('\nCidade: %s\nDist.: %d\nOSM: %s\n'):format(item[1], item[2], item[4]))
for _, opcao in ipairs(item[5]) do
comparacao_file:write('CNEFE: ', opcao, '\n')
end
end
comparacao_file:close()
Muito interessante a otimização, Fidelis, e ficou muito bem programado em Lua. Vou incluir a otimização no programa em Python.
O grande problema de levenshtein são logradouros referenciados por números e/ou letras, onde o número de caracteres do logradouro <5. Novamente, olhem o caso de Águas Lindas de Goiás (grande DF).
Para isso, quando comparar dois endereços, geralmente eu realizo a expansão do numeral em sua representação ortográfica, por exemplo, rua 10 se transforma em rua dez (ainda com <5 caracteres e ruim pro levenshtein).
Uma alternativa melhor é simhash (minhash) com shingling, pra medida de similaridade e não utilizar edit distance (levenshtein).
Links:
-
SimHash: google
-
MinHash: en.wikipedia
-
w-shingling: en.wikipedia
Seria possível dizer de forma simples o que é cada um?
Sim, claro!
Similarity Hashing, é uma técnica de cryptografia onde strings que tenham alguma similaridade são codificadas em hashes com prefixo coincidente.
A técnica chama-se Locality Sensitive Hashing, é parecido com Geohashing, só que aplicado para textos.
É o algoritmo utilizado pela maioria dos portais de busca para detecção de Near Duplicates.
Minhash é a versão simplificada de Simhash e utiliza o coeficiente de Jaccard (união/intersecção) para o cálculo da similaridade.
w-shigling é utilizado na fase de pré-processamento da similiaridade, apenas para aumentar o espaço de busca, e também para lidar com typos, etc.
djeps, os hashs então são ordenados por um “cliente” (camada acima, a de interface com usuário, por exemplo) como sendo strings?
#!/usr/bin/python
# coding:utf-8
import re, math
from collections import Counter
from itertools import izip, islice, tee
a = "Rua Nossa Senhora das Graças"
b = "Rua Nsa. Sra. das Graças"
c = "R. N. Sa. das Graças"
N = 2
a3 = izip(*(islice(seq, index, None) for index, seq in enumerate(tee(a, N))))
b3 = izip(*(islice(seq, index, None) for index, seq in enumerate(tee(b, N))))
c3 = izip(*(islice(seq, index, None) for index, seq in enumerate(tee(c, N))))
WORD = re.compile(r'\w+')
def get_cosine(vec1, vec2):
intersection = set(vec1.keys()) & set(vec2.keys())
numerator = sum([vec1[x] * vec2[x] for x in intersection])
sum1 = sum([vec1[x]**2 for x in vec1.keys()])
sum2 = sum([vec2[x]**2 for x in vec2.keys()])
denominator = math.sqrt(sum1) * math.sqrt(sum2)
if not denominator:
return 0.0
else:
return float(numerator) / denominator
def text_to_vector(text):
words = WORD.findall(text)
return Counter(words)
def simhash(tokens, hashbits=32):
if hashbits > 64: hashbits = 64
v = [0]*hashbits
for t in [x.__hash__() for x in tokens]:
bitmask = 0
for i in xrange(hashbits):
bitmask = 1 << i
if t & bitmask:
v[i] += 1
else:
v[i] -= 1
fingerprint = 0
for i in xrange(hashbits):
if v[i] >= 0:
fingerprint += 1 << i
return fingerprint
def similarity(a, b, hashbits=32):
# Use Hamming Distance to return % of similar bits
x = (a ^ b) & ((1 << hashbits) - 1)
tot = 0
while x:
tot += 1
x &= x-1
return float(hashbits-tot)/hashbits
print "SIMHASH Simliarity between \""+a+"\" and \""+b+"\" is",similarity(simhash(a3),simhash(b3))
print "COSINE Simliarity between \""+a+"\" and \""+b+"\" is",get_cosine(text_to_vector(a),text_to_vector(b))
Pra entender, vejam esse post aqui: https://liangsun.org/posts/a-python-implementation-of-simhash-algorithm/
Apenas para evidenciar a relevância deste projeto, o Oliver Kühn, colaborador do OpenStreetMap na Alemanha e palestrante no evento da última quarta-feira em São Paulo, contou que um dos fatores que alavancou o OSM por lá foi justamente uma comparação desse tipo entre o OSM e outra fonte de dados, de forma a gerar um índice de completude entre as diferentes cidades e mesmo entre diferentes bairros de uma cidade. Dessa forma, com as cidades ordenadas, os mapeadores se sentem mais compelidos a fazer a sua cidade e o seu bairro subirem na tabela.
No caso, a lista de onde se vai referenciar os dados (no caso, o CNEFE) não precisava nem ao menos ser georeferenciada, podendo ser apenas uma lista de ruas por bairro/cidade. Se não me engano, era o caso na Alemanha - ou seja, eles não podiam copiar da outra fonte para o OSM diretamente, apenas comparar para ter uma ideia de quantas ruas ainda faltavam.
Veja mais detalhes em http://qa.poole.ch/ch-roads/ e http://wiki.openstreetmap.org/wiki/OSM_-_GWR_Street_and_Place_Names_Comparison.
[]s
Arlindo