est-ce possible de regrouper un tableau de chaînes en fonction de la similitude de Ruby

Question

J'ai mis en place une méthode rubis personnalisé qui regroupe un texte similaire en utilisant des boucles,

array = ["South East Queensland", "Wide Bay Burnett", "Margaret River", "Port Pirie", "Gippsland", "Elizabeth", "Barossa"] 
similarity_group = [] 
similarity_percentage = 60.0 

array.each do |first_text| 
    results.each do |second_text| 
    result = first_text.upcase.similar(second_text.upcase) 
    if result >= similarity_percentage 
     ... 
     ... 
     ... 
    end 
    end 
end 

considèrent la mise en œuvre ci-dessus pour l'élément 2000, puis groupe il en coûtera 4000000 itérations, car chaque élément se vérifie les uns les autres.

Y a-t-il une solution ou des gemmes performantes ou une bibliothèque comme grouper un groupement en vrac en fonction de leur similitude.

(j'utiliser le même élément de tableau pour la vérification de similitude)

d'attente

exemple: [array1].similarity([array1])

Answer 1

Je pense que vous êtes à la recherche clustering basée sur la distance de chaîne (par exemple Levensthein). De votre code, il semble que similar est déjà implémenté, il doit donc être clair quelle distance vous envisagez.

Pour le regroupement, ces twogems pourraient aider. Le problème est hard cependant, donc votre O (n ** 2) n'est pas si mauvais en comparaison. Vous pouvez éviter de comparer les paires de chaînes deux fois en vérifiant simplement que string1 > string2 avant de calculer la distance. Vous auriez besoin de (2000*1999)/2 itérations au lieu de 2000**2.

Answer 2

J'ai une solution matricielle que j'ai utilisée dans le passé pour comparer des ebooks, car ceux-ci sont assez volumineux et prennent du temps à traiter j'ai résolu que premièrement avec une matrice, plus tard j'ai utilisé un index sur une valeur des livres qui était aussi précis et beaucoup plus rapide. Je pourrais chercher la solution matricielle pour vous mais j'ai une autre routine simple basée sur levenshtein qui ressemble beaucoup à ce que vous voulez accomplir, en créant un tableau de similarité (un hachage ici).

Je publie la version de travail de mon script comme dans ma bibliothèque de scripts, donc vous voudrez probablement en adapter une partie. Je l'ai utilisé comme une réponse précédente sur this question. Vous pouvez par exemple construire un tableau de la même manière.

require 'levenshtein' 

MAX_DISTANCE, COMPENSATION = 3, 5 

strings = [ 
    "Hazard Const. Company", 
    "hazard construction company", 
    "PETERSON-CHASE GENERAL ENGINEERING CONSTRUCTION INC", 
    "peterson-chase general engineering construction inc", 
    "TRAFFIC DEVELOPMENT SERVICES ", 
    "traffic development services" 
] 

result = {} 
strings.each do |s| 
    s.downcase! 
    similar = result.keys.select { |key| Levenshtein.distance(key, s) < MAX_DISTANCE+(s.length/COMPENSATION) } 
    if similar.any? 
    result[similar.first] += 1 
    else 
    result.merge!({s => 1}) 
    end 
end 

p result 
# {"hazard const. company"=>2, "peterson-chase general engineering construction inc"=>2, "traffic development services "=>2}