LSH : Plus proches voisins approximatifs pour des mots , expressions ou documents

Comment effectuer des comparaisons de mots avec des listes de très grande taille tout en supportant des erreurs d’orthographe ?

Comment comparer des documents textes entre eux et dire quelles sont les documents les plus proches pour chaque document ?

Voici des questions qui peuvent se poser de manière récurrente lors de la manipulation de données dans la vie de tous les jours d’une entreprise. Par exemple, on peut chercher à concaténer deux bases de données clients avec dans les deux bases les noms, prénoms tout en se protégeant contre les fautes d’orthographe. On peut aussi vouloir rechercher des similitudes entre deux documents d’un site ou deux textes.

Blue DME a aussi été confronté à des problématiques de travaux sur des chaînes de caractères, comme la fusion de listes en prenant en compte les erreurs possibles. C’est pourquoi nous avons regardé l’état de l’art sur ce sujet et nous allons analyser une démarche permettant de traiter différents cas d’utilisations avec un algorithme, l’algorithme dit LSH que nous allons présenter plus en détail dans cet article.

Méthodologie et plan 

 

Les questions introductives en gras constituent un cadre de réflexion important et explicite ce que nous voulons faire. Il conviendra de toujours les avoir à l’esprit durant la lecture de cet article.

Pas à pas, nous balayerons les concepts fondamentaux et mettrons en place une méthodologie et un algorithme robuste, efficace et automatisable pour traiter des problèmes de comparaisons de mots, listes de mots et expressions avec de grands volumes de données.

La première partie sera consacrée à des exemples pour mieux cerner les problèmes qui se posent.  La deuxième partie permettra de donner un algorithme naïf permettant de répondre à nos questions tout en étant peu performant. Ensuite, la dernière partie introduira l’algorithme LSH et son fonctionnement et traitera de son application pour répondre à notre problématique.

I. Algorithme naturel

Ici, nous allons essayer de faire une comparaison de listes de mots à la main  ce qui nous permettra de réfléchir un algorithme et un pseudo code permettant de faire cela, de manière automatique.

On dispose des 4 listes de mots suivantes :
Liste numéro 1 = [tomate, fromage, champignon, jambon]
Liste numéro 2 = [mozzarella, tomate, jambon, fromage, champignon, artichaut]
Liste numéro 3 = [cochon, chevreuil, bœuf, veau, agneau]
Liste numéro 4 = [veau, agneau, saumon, bœuf, poulet]

Si l’on devait regrouper par paire les listes précédentes ou si l’on devait dire pour chaque paire quelle est la liste qui lui ressemble plus, intuitivement, on regrouperait la liste 1 avec la liste 2 et la liste 3 avec la liste 4.

Quelles actions se sont opérées dans notre cerveau pour parvenir à ce résultat pour arriver à ce résultat ?
Nous avons lu les mots présents dans chacune des listes puis nous avons comparé ces mots pour chaque paire de la liste en déterminant des mots se trouvant dans chacune des listes 1 et 2 (idem pour les listes 3 et 4).

Une même méthode peut s’appliquer pour une phrase en regardant le même nombre de mots, pour une phrase ou encore pour deux mots, en comparant les lettres.
Par exemple, on peut dire que les mots ‘chiens’ et ‘chien’ sont proches car ils présentent seulement une seule lettre de différence entre eux.

Ainsi, bien qu’il n’existe pas une distance formelle (comme c’est le cas pour des numériques avec une relation d’ordre) entre des mots, phrases, listes de mots, documents textes ou pages web, l’être humain peut  intuitivement établir des similitudes.

Les exemples précédents nous sont utiles pour définir, de manière intuitive, un algorithme que nous pourrons alors utiliser dans le lange de notre choix, avant de pouvoir réaliser cela, il convient de définir quelques notions fondamentales nécessaires afin de pouvoir travailler par la suite et d’écrire un premier algorithme répondant à nos interrogations.

 

II. Exactitude entre des mots et algorithme naïf

Apres avoir établi une méthodologie à la fin de la partie précédente, nous allons définir la notion intuitive de ressemblance entre les mots. Pour cela, nous allons travailler avec une notion de distance mathématique entre les mots. C’est une fonction mathématique qui prend en argument deux mots et qui renvoie une valeur numérique symbolisant la distance entre ces deux mots. Plus cette distance est grande, moins les mots se ressemblent. Il en existe plusieurs, la plus connue étant la distance de Levenshtein que je vais présenter ci-dessous :

 II.1.Distance de Levenshtein

On appelle distance de Levenshtein entre deux mots M et P le coût minimal pour aller de M à P, en effectuant les opérations élémentaires suivantes :
-substitution d’un caractère de M en un caractère de P
-ajout dans M d’un caractère de P
-suppression d’un caractère de M
On associe ainsi à chacune de ces opérations un coût. Le coût est toujours égal à 1, sauf dans le cas d’une substitution de caractères identiques.

II.2.Exemple

Si M = « examen » et P = « examen », alors LD (M, P) = 0, car aucune opération n’a été réalisée.
Si M = « examen » et P = « examan », alors LD (M, P) = 1, parce qu’il y a eu un remplacement (changement du e en a)

La distance de Levenstein est assez coûteuse en termes d’opérations et de mémoire. Elle donne, de plus, des résultats exacts en termes de distances entre deux chaines de caractères.

II.3.Utilisations

L’utilisation des algorithmes et des concepts que nous allons présenter dans les prochains paragraphes peut s’appliquer aux questions que nous avons posés dans l’introduction.
En effet, il est possible de gérer les fautes d’orthographes avec des comparaisons entre mots, de pouvoir effectuer du matching entre deux listes de mots ou d’expressions, de comparer des documents web ou textes et de pouvoir les regrouper en clusters un peu de la même manière qu’avec un algorithme k-means.

 

II.4.Algorithmes

Apres avoir introduit différents concepts, voici un algorithme assez simple pouvant utiliser des langages comme Spark pour faire du calcul distribué en utilisant des structures de type RDD.

On dispose de 2 listes  de grandes tailles, respectivement de taille n et m. Dans chacune de ces listes se trouvent des mots ou plusieurs mots réunis en une seule phrase. Il suffit d’effectuer un produit cartésien entre les 2 listes puis pour chaque élément de lui associer les mots les plus proches en termes de distance. Cette algorithme répond à la question de la jointure entre deux listes mais n’est pas très performant comme on va le voir dans la discussion.

II.5.Discussions

Ici, en utilisant un produit cartésien entre des mots avec une distance qui compare deux mots, comme la distance de Levenshtein, nous avons une complexité au moins en  O(n²)  ,avec n notre nombre de mots ou d’expressions. En réalité, selon la méthode choisie, il faudrait prendre ne compte à chaque fois le nombre d’opérations nécessaires pour effectuer une distance entre deux mots chez Levenshtein (qui dépend de la longueur des mots).

Ainsi, dans le cadre de travaux pour Blue DME avec des listes de plusieurs millions de mots à comparer, le temps nécessaire pour effectuer ces opérations de manière exacte est beaucoup  trop élevé, c’est pourquoi j’ai décidé de rechercher une autre méthode permettant d’optimiser la performance, quitte à avoir quelques approximations parfois. C’est l’algorithme LSH que nous allons présenter dans la partie suivante.

Pour effectuer des comparaisons avec un grand nombre de données, l’utilisation de distance comme celle-ci s’avère problématique. C’est pourquoi nous allons nous intéresser à une autre méthode qui permet de trouver, de manière non exacte, une approximation des plus proches voisins d’un mot, d’une expression ou d’un document. C’est la méthode LSH qui sera introduite dans la partie III.

 

III. Un nouvel algorithme : LSH

Dans ce paragraphe, après avoir remarqué les faiblesses des techniques utilisant un produit cartésien et des distances comme celles de Levenshtein, nous allons présenter l’algorithme LSH qui pourra répondre à nos besoins.

III.1.Encodage d’un mot

Tout d’abord, nous allons montrer que l’on peut calculer des distances entre des mots/listes de mots/expressions en utilisant un encodage de ces mots en vecteur numérique, ce principe  sera utilisé pour la présentation de le l’algorithme LSH

Il existe plusieurs manières/techniques pour encoder un mot.
On peut ne considérer que les lettres de l’alphabet : ainsi le mot « chien » aura comme vecteur d’encodage le vecteur de taille 26 (car il existe 26 lettres différentes dans l’alphabet) suivant :
[0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0] car on retrouve un c, un e, un h, un i, et un n.
Cette méthode permet de travailler avec des mots ayant pour vecteur d’encodage une dimension assez faible (de taille 26). Cependant, on ne tolère pas des anagrammes, le mot niche ayant exactement le même encodage que le mot « chien ».

Nous pouvons augmenter la dimension et raffiner le modèle alphabétique, en considérant ici non seulement les lettres de l’alphabet présent dans un mot, dans une expression, mais aussi les paires de l’alphabet. Ainsi, il est presque certain de tomber sur un mot unique qui se caractérise par des paires.

Dans notre cas, « chien » et « niche » ne s’encode plus du tout de la même manière puisque nous disposons d’un vecteur de taille 702 (les 26 premières valeurs représentent l’encodage suivant les lettres uniques et le reste représente l’encodage suivant les paires aa, ab,…, zy, zz).

Cette méthode s’applique mieux lorsque l’on compare des phrases courtes ou des mots.

 

III.2.Encodage d’une expression

Lorsqu’on travaille avec des listes d’expressions, on peut, pour les encoder, considérer tous les mots uniques, que l’on retrouve dans celles-ci, en tant que colonne.
Par exemple, si je veux comparer les 2 phrases « Je serai en retard ce matin » et « Je serai en avance ce soir », on va les encodera de la manière suivante :
La liste des mots uniques dans un ordre choisi est :
[Je, serai, en, retard, avance, ce, matin, soir]
Ainsi la 1ère phrase s’encode de la façon suivante :
[1, 1, 1, 1, 0, 1, 1]
La 2ème phrase s’encode de la façon suivante :
[1, 1, 1, 0, 1, 1, 0, 1]
Cette méthode est efficace pour comparer des documents possédant beaucoup de mots.

Lorsqu’on veut comparer beaucoup de documents ou des documents avec un grand nombre de mots pour trouver leurs plus proches voisins, nous devons manipuler des données numériques et des matrices de grandes dimensions -même si elles peuvent être très creuses. Il existe de nombreux modules en python, en R et dans d’autres langages pour manipuler des matrices creuses. En python, on retrouve par exemple le module parse.

III.3.Cas d’utilisations

Dans le langage Python, les mots, les phrases et les gros documents sont des chaînes de caractère avec le même type. Il convient ainsi lorsque l’on travaille avec des chaines de caractères, de savoir ce que l’on veut faire exactement pour effectuer un bon encodage en fonction de notre problème.

Si on veut faire du matching, une jointure entre deux tables de données entre des mots ou des phrases courtes, il est préférable d’utiliser un encodage avec les paires d’alphabet.

Pour faire des comparaisons avec des documents, il est préférable d’utiliser l’encodage présenté dans la partie II.2.

 

III.4.Distance entre vecteurs encodés :

Nous disposons de plusieurs distances entre les vecteurs qui sont des mots encodés. Nous pouvons utiliser des distances classiques (distance euclidienne, par exemple)

Cependant, nous allons utiliser pour l’algorithme LSH (voir partie III)  la distance « cosine » dont la définition est la suivante :

Cosine(u,v)=<u,v>/(Longueur de u*Longueur de v)

III.5.Pseudocode :

Ce pseudo-code est la traduction avec explications du pseudocode de l’article [1] sur LSH. Les lecteurs voulant approfondir le sujet peuvent s’y référer directement.

On dispose d’une liste de mots que l’on encode en numérique, comme vu précédemment. Toute la question est de savoir comment, avec quelle précision. Le résultat de l’algorithme sera différent selon le type d’encodage. Dans l’article [1], l’encodage prend des mots en colonnes et concerne surtout des documents textes.
Nous avons alors une matrice de taille n,k (généralement de  grande dimension).

On cherche à  trouver toutes les paires possédant une similarité (donc un cosine) supérieure à un certain seuil.
On choisit un nombre d (d doit être inférieur à k et très inférieur à k si k est grand), qui va représenter notre nombre de fonctions de hashage. Les fonctions de hashage dépendent chacune respectivement d’un vecteur gaussien généré aléatoirement, ici des vecteurs gaussiens de dimensions k.
Nous allons calculer le produit de scalaire entre notre vecteur gaussien et nos mots encodés. Si le résultat est positif, on entre 1, sinon on entre 0.
On fait cela pour les d vecteurs générés aléatoirement. On obtient donc un nouveau vecteur de taille d encodé en 0 et 1.
A ce stade, nous disposons de n vecteurs encodés avec d bits (vecteurs de taille d avec 0 ou 1).

 

On veut implanter/calculer, de manière rapide, une distance de Hamming.

 

Pour cela, nous allons prendre les index respectifs de chacun des mots encodés et appliquer une fonction qui va utiliser l’opération modulo.
Cette fonction est :

(ax+b) mod p avec p un nombre premier, x l’index du mot, a et b sont choisis au hasard, inférieur à p.

Nous appliquons q permutations avec des paires de a et b différentes. Puis, nous choisissons p. Pour chaque permutation, nous allons trier le vecteur obtenu dans l’ordre.
Pour chaque vecteur trié, nous allons calculer la distance de Hamming entre notre vecteur et B (paramètre à définir) de ses plus proches voisins dans notre liste triée. Si la distance est supérieure au seuil (paramètre également à définir), nous gardons cette paire et la considérons comme convenable.

III.6. Illustration :

 

On dispose de 3 phrases :

Phrase 0 =  » je me lève à l’heure qui me plaît  »

Phrase 1=  » je me lève à l’heure  »

Phrase 2= « je me lève tôt le matin  »

On enlève les accents et d’autres caractères qui ne sont pas dans l’alphabet. Nos 3 phrases deviennent donc :

Phrase 0 =  » je me leve a l heure qui me plait  »

Phrase 1=  » je me leve a l heure  »

Phrase 2= « je me leve tot le matin  »

 

Ici, nous allons réaliser un encodage en mettant en colonnes chacun des mots. Si la phrase 0 possède le mot de la colonne alors on peut la remplir, sinon on entre  0.

On indexe chaque phrase :

Phrases

 

Ensuite, on déroule l’algorithme  pour obtenir les phrases les plus proches. Il est évident que le gain de temps n’est pas intéressant avec 3 phrases et si peu de mots. Néanmoins, en prenant beaucoup de phrases, nous avons un grand nombre de mots et nous travaillons donc en très grande dimension. Dans ce cas, l’algorithme se révèle très efficace et puissant. On peut appliquer le même principe pour des documents ou pages web au lieu de phrases.

Ici, nous avons travaillé avec des mots pour les colonnes au lieu des lettres de l’alphabet ou des paires de lettres.

III.7.Complexité :

On se replace dans l’exemple donné à la fin de la partie II, à savoir une comparaison de 2 listes de mots de tailles respectivement m et n.

Ici, sans utiliser d’algorithme approximatif LSH, en utilisant juste des mots encodés, nous avons déjà vu que la complexité était au moins  en  O(n²)

Ici, avec notre algorithme, on obtient un algorithme en O((m+n)k)

Nous allons voir sous quelles conditions l’algorithme LSH est plus intéressant pour nos travaux. Cela consiste à étudier les fonctions donnant la complexité en fonction du volume de données. Pour des raisons de commodités, on va supposer que m=n, c’est-à-dire que les deux listes que l’on veut comparer ont la même taille. Cela revient à comparer les deux fonctions    n²  et  2nk  avec k le nombre de colonnes servant à l’encodage. On peut considérer le cas, k=26 ou k=702 plus précis.

Dans ce cas, on compare n²   et 2n*702=1404n  .

 

Graphe

 

 

Voici un  graphique résumant la comparaison de la complexité entre nos deux algorithmes proposés. LSH est en bleu et l’algorithme de la partie II utilisant un produit cartésien est en bleu. On voit que le gain en temps de calcul n’est pas très important jusqu’à des listes de données de taille 1500, mais qu’au-dessus, l’utilisation de LSH permet de gagner un temps précieux.

Pour des cas d’utilisation en grands volumes de données, par exemple 1 millions de mots dans une liste lors d’une comparaison, le nombre d’opérations nécessaires pour LSH est donc d’environ  1 404 000 000 soit plus d’un milliard d’opérations. En revanche pour l’algorithme naïf utilisant un produit cartésien, le nombre d’opérations nécessaire est  d’environ 1 000 000 *1 000 000 =1 000 000 000 000 soit 1000 fois plus d’opérations. Notre algorithme LSH  est donc pour des grands volumes de données au moins 1000 fois plus rapide.

 

Je préconise donc pour comparer deux listes de mots, faire du matching pouvant gérer des erreurs, des fautes d’orthographe et pouvant être gérée de façon automatisée et de manière industrielle, d’utiliser LSH de la façon suivante :

  1. Utiliser correctement l’algorithme LSH qui permet à partir d’une seule liste de donner les éléments les plus proches pour chacun des éléments. Pour ce faire, regrouper les 2 listes de mots

Illustration :

Voici les 2 listes de départ :

Tab1                  Tab2

On les regroupe et on peut alors passer à l’étape d’encodage :

 

Tabres

  1. Encoder les mots de façon pertinente (avec les paires de lettres ou juste avec l’alphabet mais c’est moins précis)
  2. Faire tourner l’algorithme et redonner les bons mots pour chacun des mots

 

III.6.Implémentation :

III.6.1Package LSH :

Il existe plusieurs implémentations et différents packages dans le langage Python. Nous allons ici en présenter une.

Tout d’abord, nous allons télécharger le package LSHash sur Python et l’installer. Celui-ci est assez facile d’accès et est facilement compréhensible avec une prise en main rapide.

Pour une brève présentation de son fonctionnement, on importe en Python le package. Ensuite, on génère avec la fonction LSH un encodage de référence-le nombre de fonctions de hashages et la dimension des mots encodés devant être stipulés et restés constants, tout au long de l’algorithme. Il faut donc que chaque mot encodé comme « absolu » et « absolument » ait un vecteur d’encodage de même taille.

Ensuite, on lui transmet un nombre de mots encodés qui seront stockés. On choisit ensuite un mot nouveau ou déjà présent et l’algorithme nous renvoie une approximation des plus proches voisins. Il peut nous renvoyer une liste vide dans certains cas et les mots/expressions les plus proches ne sont pas toujours les mêmes en sortie. Cependant, cela peut nous poser des problèmes, que nous allons essayer de résoudre.

Code python pour encoder des mots en considérant les paires de l’alphabet :

 

def createpaireencode(string) :

alphabet='a b c d e f g h i j k l m n o p q r s t u v w x y z'

vecalphabet=alphabet.split(' ')

pairevec=vecalphabet+[(x+y) for x in vecalphabet for y in vecalphabet ]

d=[]

for i in pairevec :

d=d+ [string.count(i)]

return (string,d)

 

Code python pour encoder des mots avec une liste de mots, utilisable pour comparer des documents :

 

Code python pour une bonne optimisation avec LSH sans utiliser des fonctionnalités RDD mais seulement des listes :

 

def superoptLSH(lis,lis1,p,q,r,s,v)

maxi=int(702)

ash=LSHash(p,maxi,r)

bbb= [ createpaireencode(normalize(unicode(j))) for j in lis ]

bb= [q[1] for q in bbb ]

aaa=[ createpaireencode(normalize(unicode(j))) for j in lis1 ]

aa=[ p[1] for p in aaa ]

for z in bbb :
   ash.index(z[1])
li=[]

for i in aaa :

if i[0] in lis :

li=li+[(i[0],[i[0]],True)]
else :
   
dragon={} 

for j in range(s) :

dd=ash.query(i[1],None,'cosine')
ddd=dd
for k in range(len(dd)):

tro=list(dd[k][0])

if tro in bb :

g=bb.index(tro)

f=bbb[g][0]
ddd[k]=f

res1=(i[0],ddd)
kk=res1[1]


for key in kk :

if key in dragon :

dragon[key]+=1

else :

dragon[key]=1


vecres=[ (o[0],o[1]) for o in dragon.items() ]


newres=sorted(vecres,key=lambda x : x[1],reverse=True)


if newres==[] :

li=li+[(i[0],['pas trouve'],False)]

else :


li=li+[(i[0],[newres[0][0]],False)]


return li

III.6.2.Exemple :

 

Nous allons prendre deux listes de prénoms et nous allons pour chaque prénom de la liste 1, trouver les plus proches prénoms dans la liste 2. Voici notre liste 1 et notre liste 2.

On lance l’algorithme et obtient comme résultat :

 

Prenom

 

On voit alors que les erreurs d’orthographe entre deux prénoms sont bien gérées. Si deux prénoms se ressemblent comme Amanda et Amandine, ils sont regroupés. Si un prénom ne ressemble à aucun autre, nous n’avons pas de résultat.

 

On peut utiliser le même algorithme pour comparer des adresses mails par exemple : il suffit de prendre en compte les caractères @ et   .

Cela peut être très utile pour faire du matching en grande dimension entre deux bases de données ou utiliser une opération de jointure entre deux bases de données, en prenant en compte différentes écritures possibles, des fautes d’orthographe.

III.7 Pour aller plus loin :

III.7.1. Implémentation Scala

 

Une présentation très complète de l’algorithme LSH avec tous les fondements mathématiques sous-jacents se trouve dans l’article [4].Il existe d’autres implantations en Python de l’algorithme LSH.

Il existe également une structure de LSH utilisant les fonctionnalités Spark (notamment le calcul distribué utilisant des structures de RDD), l’algorithme est alors écrit directement en Scala. Vous pouvez le trouver à la page suivante :

https://github.com/marufaytekin/lsh-spark

 

III.7.2. Plus de précisions

Comme l’algorithme LSH est un algorithme non exact (il utilise en effet des fonctions de hashage et des simulations de vecteurs gaussiens), j’ai remarqué, après plusieurs itérations du même algorithme, que les résultats de l’algorithme ne sont pas toujours identiques. En effet, si on veut chercher les mots les plus proches d’un mot choisi, en utilisant l’algorithme Python vu précédemment, les mots les plus proches en sortie ne sont pas toujours les mêmes.

Pour contourner ce problème, nous pouvons utiliser une méthode populaire Spark par exemple, le « WordCount », qui consiste à itérer l’algorithme un certain nombre de fois (10 fois par exemple), et de compter tous les mots en sortie à chaque itération. Ensuite, on compte le nombre de mots supérieurs à un seuil (ici 5 par exemple avec 10 itérations). De cette façon, nous avons de résultats plus précis en sortie.

 

CONCLUSION

 

Un pseudo code et son implémentation dans le langage Python a été réalisés avec une discussion sur les forces et faiblesses. C’est un bon algorithme pour trouver de manière quasi-approximative les plus proches voisins d’un mot dans une liste (avec une complexité en pour réaliser cela sur tous les mots d’une même liste). Cependant, cet algorithme n’utilisant pas des fonctionnalités Big Data comme les RDD dans Spark, il n’est pas optimal en terme de complexité, mais le pseudo code et les articles permettent d’en implanter un en Python ou d’en prendre un déjà écrit en Scala. La définition et le choix de certains paramètres est difficile, comme le nombre de fonctions de hashage, le choix de l’encodage qui dépend de la situation.
Compte tenu des enjeux Big Data (manipulation de grandes bases de données), d’autres algorithmes peuvent être possibles/ sont envisageables. Ces algorithmes peuvent toujours être améliorés et font l’objet de travaux de R&D chez Blue DME.

En conclusion, nous avons donc fourni une méthodologie et une démarche dans cet article qui peut s’appliquer à de nombreux problèmes : comparaison de listes de mots/de documents avec prise en compte d’erreurs possibles, de fautes d’orthographe. Il convient de toujours faire attention au cadre de travail pour pouvoir adapter au mieux notre algorithme LSH aux  besoins. L’algorithme est facilement adaptable de manière automatique et industrielle.

 

Cette méthode semble promise à un bel avenir, puisqu’elle permet de traiter de gros volumes de données (1Million * 1 Million) afin d’effectuer des comparaisons massives.Cette méthode, appliquée de façon itérative, permet d’avoir des résultats quasi-exacts tout en supportant des approximations ou des erreurs d’orthographes.La souplesse de l’algorithme permet de l’appliquer dans des situations différentes comme des comparaisons de documents, du matching entre listes de mots de grande taille. Un algorithme Python a été proposé et plusieurs packages existent, donnant des résultats plus ou moins bons.

 

Sources: 

[1] Randomized Algorithms and NLP: Using Locality Sensitive Hash Function for High Speed Noun Clustering

http://delivery.acm.org/10.1145/1220000/1219917/p622-ravichandran.pdf?ip=84.14.146.196&id=1219917&acc=OPEN&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&CFID=720208782&CFTOKEN=77490098&__acm__=1444398751_ba4764fbfa93ef2cb282c7d55beefb6b

 

[2] https://rajmak.wordpress.com/2014/12/22/locality-sensitive-hashing-lsh-map-reduce-in-python/

 

[3]   Kay Zhu: Package lshash,

https://pypi.python.org/pypi/lshash/0.0.4dev

 

[4] Hashing for Similarity Search: A Survey Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji

http://arxiv.org/pdf/1408.2927.pdf