Nesse caso, eu me preocupo muito pouco com a licença porque é um programa muito simples (e pouco pensado). O único “pulo do gato” realmente é usar a distância de Levenshtein, mas sob uma licença restritiva bastaria mudar o algoritmo pra qualquer outro parecido (existem vários) para que a licença já não tivesse mais efeito. Além disso, o algoritmo não resolve o problema automaticamente: ele simplesmente produz uma saída mais útil ao processo de revisão manual.
Quando eu falo “dono” nesse contexto, não é no sentido de “privatizar” o código. Mas no sentido do projeto ter uma orientação. Para ele ter, é necessário ao menos uma pessoa. Ela também viabiliza o ponto de encontro dos interessados em expandir o projeto.
Quando eu me preocupo em comentar sobre a autoria dos commits, não é, nesse contexto, sobre você ter exclusividade de utilização do código ou coisa que o valha. É preocupação com o devido crédito autoral. Você teve a iniciativa de programar essas linhas. Dispendeu tempo nisso. Seria muito chato se todo mundo ficasse achando que o mérito foi do alexandre-mbm por causa da assinatura nos commits.
Sobre esse tempo que estamos “gastando”. Pelo contrário, é um dos poucos casos em que me vejo “investindo” tempo na cadeira. Eu entendo que estamos tendo uma conversa importante. Tanto para esclarecer sobre nossas pessoas (e registrar isso) como para possivelmente influenciarmos as opiniões ideológicas um do outro. Está me parecendo que você está achando que estou trazendo um espírito de software privativo. Eu estou tentando lhe dizer que não, mas que me preocupo com alguns dos direitos autorais. É injusto um “Marcos” sair por aí dizendo — ou deixando as pessoas inferirem erroneamente e quase inevitavelmente — que foi ele o criador do kernel Linux. Todos sabemos que foi o Linus…
O software pode crescer. Por isso eu me preocupo com a licença. Parece que você está olhando somente para o que já está criado, e não para o que será ou pode ser ainda criado. Como quero ser apenas um colaborador, vou tentar seguir sua linha de licenciamento também para algum módulo (outra funcionalidade) que eu venha a escrever. Apesar de eu ter muita vontade de pensar melhor o licenciamento do software que eu publico. Pode ser que lhe incomode ter o parsing dos arquivos em outra licença no mesmo repositório, não é?
Mas eu estou lendo sobre a unlicense e entendendo seu espírito de economia de tempo… apesar de não concordar com ele no geral, posso aceitá-lo em alguns casos.
Bem, nesse caso, vamos pruma licença BSD ou MIT ou algo do gênero.
Eu só não pensei na licença ainda porque estamos em fase de brainstorm, e nessa fase eu não quero interromper o fluxo das idéias pra aprender a usar o Git :D. Que aliás, até já sei usar, 95%. 
Por exemplo, já estou programando outra alteração a partir do feedback que está vindo da talk-br.
Entendo e compreendo suas motivações.
Eu li brevemente MIT License, BSD licenses e ISC license. Faz parte de leituras que eu já tinha feito no decorrer de anos mas que precisam sempre ser refrescadas.
No contexto em que estamos, simpatizei com University of Illinois/NCSA Open Source License e mais ainda com a simplicidade (que, é verdade, pode ser problemática, mas vamos lá) da Expat License. Resumindo: esta é permissiva mas pede um “respeito” ao aviso de copyright nos fontes.
Também cheguei novamente à página “Various Licenses and Comments about Them” da Free Software Foundation e, só para constar: lá eu tive um olhar especial para a Expat License (#Expat) seguida da Apache License, Version 2.0 (#apache2) — proteção contra patentes é algo que valorizo.
Em geral, sinto falta de uma proibição à propaganda com os nomes dos autores. Mas vamos de Expat License?
Consigo imaginar que essa conversa está perto de lhe aborrecer ou já lhe aborreceu. Mas, se você parar para pensar, verá que ela é importante. Quer dizer… eu espero que isso aconteça 
Estou torcendo por isso! 
Não que eu esteja aborrecido, Alexandre, mas é que acho cedo demais pra se preocupar com isso. Se eu fizer amanhã ou depois de amanhã (quando o brainstorm já estiver mais finalizado), será bem melhor (pra mim).
Eu acho interessante o aspecto de “versionar” controladamente as ideias (implementações). Fique a vontade. Não vou mais lhe atrapalhar, então.
Além das outras possibilidades de expansão já citadas, quero lembrar a todos os interessados a existência da Consulta da base de CEP dos Correios.
A propósito, Fernando. Ontem mesmo eu conheci awnist/distance (Coffeescript). Ele é UNLICENSED. Suponho que seria o tipo de projeto no qual você estava pensando. Como eu não estou ocupado com as linhas código, fico a imaginar o crescimento disso que você começou no sentido das aplicações concretas ao OpenStreetMap. Na minha opinião, seria melhor a comunidade tender a ter UM único ponto de reunião de esforços, se estes esforços podem ser somados para alcançar um mesmo resultado lá na frente.
Olá, post muito interessante. Estou com idéias parecidas de cruzar o CNEFE e o OSM. Como não é exatamente a mesma coisa, abri em um outro tópico:
http://forum.openstreetmap.org/viewtopic.php?pid=409082#p409082
talvez te interesse
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