Un code efficace Ruby pour trouver le plus court préfixe pour chaque mot qui est unique parmi les mots

Question

Je tables de hachage similaires (mais beaucoup plus grands):

h={ 
    "Wilhelm_Conrad_Röntgen": "http://www.example.com/w2xtt4w/001_1901.jpg", 
    "Hendrik_Lorentz": "http://www.example.com/apbfksz/004_1902.jpg", 
    "Pieter_Zeeman": "http://www.example.com/d2cpwj3/007_1902.jpg", 
    "Antoine_Henri_Becquerel": "http://www.example.com/g8sueyg/010_1903.jpg", 
    "Maria_Skłodowska-Curie": "http://www.example.com/gfcgur8/013_1903.jpg", 
    "Lord_Rayleigh": "http://www.example.com/dcjiwq8/016_1904.jpg", 
    "Joseph_John_Thomson": "http://www.example.com/4a66bc9/019_1906.jpg", 
    "Gabriel_Lippmann": "http://www.example.com/xjefgoa/022_1908.jpg", 
    "Guglielmo_Marconi": "http://www.example.com/x359w62/025_1909.jpg", 
    "Karl_Ferdinand_Braun": "http://www.example.com/1edm469/028_1909.jpg", 
    "Johannes_Diderik_van_der_Waals": "http://www.example.com/31hpue7/031_1910.jpg", 
    "Wilhelm_Wien": "http://www.example.com/yel9iff/034_1911.jpg", 
    "Nils_Gustaf_Dalén": "http://www.example.com/iezss59/037_1912.jpg", 
    "Heike_Kamerlingh-Onnes": "http://www.example.com/8zl4uj2/040_1913.jpg", 
    "Max_von_Laue": "http://www.example.com/ta3w6rn/043_1914.jpg", 
    "William_Henry_Bragg": "http://www.example.com/u43qn5h/046_1915.jpg", 
    "William_Lawrence_Bragg": "http://www.example.com/n7gkk6e/049_1915.jpg", 
    "Charles_Glover_Barkla": "http://www.example.com/2kxxroc/052_1917.jpg", 
    "Max_Planck": "http://www.example.com/eyw7tm6/055_1918.jpg", 
    "Johannes_Stark": "http://www.example.com/gcjcv2p/058_1919.jpg", 
    "Charles_Édouard_Guillaume": "http://www.example.com/nox3s6o/061_1920.jpg", 
    "Niels_Bohr": "http://www.example.com/mo9ga29/064_1922.jpg", 
    "Robert_Andrews_Millikan": "http://www.example.com/kxq71if/067_1923.jpg", 
    "Manne_Siegbahn": "http://www.example.com/2uwhw9y/070_1924.jpg", 
    "James_Franck": "http://www.example.com/iwdavip/073_1925.jpg", 
    "Gustav_Hertz": "http://www.example.com/73mbso2/076_1925.jpg", 
    "Jean_Baptiste_Perrin": "http://www.example.com/rgugmas/079_1926.jpg", 
    "Arthur_Holly_Compton": "http://www.example.com/vy7is1v/082_1927.jpg", 
    "Owen_Willans_Richardson": "http://www.example.com/3jz5ve8/085_1928.jpg", 
    "Louis_Victor_Pierre_Raymond": "http://www.example.com/srvj8d5/088_1929.jpg", 
    "John_M_Kosterlitz": "http://www.example.com/7op2wb1/091_1929.jpg", 
    "Chandrasekhara_Venkata_Raman": "http://www.example.com/1vqqwua/094_1930.jpg" 
} 

Je voudrais trouver le plus court préfixe dans un efficace manière pour chaque clé dont le préfixe est unique parmi les clés données. En d'autres termes: avoir les préfixes plus courts chaque ligne est toujours reconnaissable dans la table de hachage. Pour cette table de hachage les préfixes les plus courts qui fait encore les lignes reconnaissables:

h={ 
    "Wilhelm_C": "http://www.example.com/w2xtt4w/001_1901.jpg", 
    "Hen": "http://www.example.com/apbfksz/004_1902.jpg", 
    "P": "http://www.example.com/d2cpwj3/007_1902.jpg", 
    "An": "http://www.example.com/g8sueyg/010_1903.jpg", 
    "Mar": "http://www.example.com/gfcgur8/013_1903.jpg", 
    "Lor": "http://www.example.com/dcjiwq8/016_1904.jpg", 
    "Jos": "http://www.example.com/4a66bc9/019_1906.jpg", 
    "Ga": "http://www.example.com/xjefgoa/022_1908.jpg", 
    "Gug": "http://www.example.com/x359w62/025_1909.jpg", 
    "K": "http://www.example.com/1edm469/028_1909.jpg", 
    "Johannes_D": "http://www.example.com/31hpue7/031_1910.jpg", 
    "Wilhelm_W": "http://www.example.com/yel9iff/034_1911.jpg", 
    "Nil": "http://www.example.com/iezss59/037_1912.jpg", 
    "Hei": "http://www.example.com/8zl4uj2/040_1913.jpg", 
    "Max_v": "http://www.example.com/ta3w6rn/043_1914.jpg", 
    "William_H": "http://www.example.com/u43qn5h/046_1915.jpg", 
    "William_L": "http://www.example.com/n7gkk6e/049_1915.jpg", 
    "Charles_G": "http://www.example.com/2kxxroc/052_1917.jpg", 
    "Max_P": "http://www.example.com/eyw7tm6/055_1918.jpg", 
    "Johannes_S": "http://www.example.com/gcjcv2p/058_1919.jpg", 
    "Charles_É": "http://www.example.com/nox3s6o/061_1920.jpg", 
    "Nie": "http://www.example.com/mo9ga29/064_1922.jpg", 
    "R": "http://www.example.com/kxq71if/067_1923.jpg", 
    "Man": "http://www.example.com/2uwhw9y/070_1924.jpg", 
    "Ja": "http://www.example.com/iwdavip/073_1925.jpg", 
    "Gus": "http://www.example.com/73mbso2/076_1925.jpg", 
    "Je": "http://www.example.com/rgugmas/079_1926.jpg", 
    "Ar": "http://www.example.com/vy7is1v/082_1927.jpg", 
    "O": "http://www.example.com/3jz5ve8/085_1928.jpg", 
    "Lou": "http://www.example.com/srvj8d5/088_1929.jpg", 
    "John": "http://www.example.com/7op2wb1/091_1929.jpg", 
    "Chan": "http://www.example.com/1vqqwua/094_1930.jpg" 
} 

Ma première tentative de trouver les préfixes plus courts pour chaque clé ou mot:

ret=h.keys.map{|k| 
    l=1; 
    while h.keys.select{|z| z=~/^#{Regexp.quote(k[0..l-1])}/}.size != 1 do 
    l+=1 
    end 
    puts "#{k} -> #{k[0..l-1]}" 
    [k[0..l-1],h[k]] 
}; 

algorithme et le code est loin d'être optimale, en fait, il est très lent même sur une machine rapide, et quand la table de hachage est beaucoup plus grande, elle est inutilisable.

Exemple hachage peut être récupérée:

require "json" 
h=JSON.load(%x{curl http://pastebin.com/raw/Cs0dTJmA}) 

Une référence rapide de deux méthode différente:

-axe des X représente la taille de hachage d'entrée/matrice, Y- l'axe est pour le temps de fonctionnement en secondes.

code final, maintenant le plus rapide et pas gourmand en mémoire:

def optimize_keys(ih) 

    h=ih.dup #for not messing with the original 
    result={} 
    bh={} 
    l=1 
    ks=h.keys.size 

    while result.size < ks do 

     h.keys.each{|k| 
      prefix=k[0..l-1] 
      bh[prefix]==nil ? bh[prefix]=[1,k] : bh[prefix][0]+=1 
     } 

     ones=bh.select{|k,v| v[0]==1} 

     ones.each{|k,v| 
       result[k]=h[v[1]] 
       h.delete(v[1]) 
     } 

     bh={} 
     l+=1 
    end 

    return result 
end 

Answer 1

Voici un algorithme

words = %w{ruby rules} 

hash1 = {} 
words.each do |word| 
    abbr = word 
    until abbr.empty? 
    hash1[abbr] = hash1[abbr] ? :ambigous : word 
    break if hash1[abbr] == :ambigous 
    abbr = abbr.chop 
    end 
end 
hash2 = {} 
hash1.each { |abbr, word| hash2[word] = abbr } 
hash2.delete(:ambigous) 

p hash2 

Comment ça marche?

• Generate tous les prefices possibles, les cartographier soit le mot entier ou :ambigous
• Inverser le hachage et depuis prefices sont en ordre décroissant de longueur du hachage inversée tracera au plus court préfixe
• Retirez le "mot" :ambigous du hash inversé

Answer 2

Vous pouvez utiliser Abbrev.abbrev pour générer une liste d'abréviations non ambiguës. Parce qu'il génère un hachage avec les abréviations comme clés et les mots comme valeurs, nous devons extraire les abréviations les plus courtes et les clés et les valeurs d'échange.

require 'abbrev' 
word_to_abbr = Abbrev.abbrev(h.keys) 
        .group_by { |k, v| v } 
        .map { |k, v| [k, v.flatten.min_by(&:length)] } 
        .to_h 

output = {} 
h.each { |k, v| output[word_to_abbr[k].to_s] = v } 

output 
#=> { 
#  "Wilhelm_C" => "http://www.example.com/w2xtt4w/001_1901.jpg", 
#  "Hen"  => "http://www.example.com/apbfksz/004_1902.jpg", 
#  "P"   => "http://www.example.com/d2cpwj3/007_1902.jpg", 
#  "An"   => "http://www.example.com/g8sueyg/010_1903.jpg", 
#  "Mar"  => "http://www.example.com/gfcgur8/013_1903.jpg", 
#  "Lor"  => "http://www.example.com/dcjiwq8/016_1904.jpg", 
#  "Jos"  => "http://www.example.com/4a66bc9/019_1906.jpg", 
#  "Ga"   => "http://www.example.com/xjefgoa/022_1908.jpg", 
#  "Gug"  => "http://www.example.com/x359w62/025_1909.jpg", 
#  "K"   => "http://www.example.com/1edm469/028_1909.jpg", 
#  "Johannes_D" => "http://www.example.com/31hpue7/031_1910.jpg", 
#  "Wilhelm_W" => "http://www.example.com/yel9iff/034_1911.jpg", 
#  "Nil"  => "http://www.example.com/iezss59/037_1912.jpg", 
#  "Hei"  => "http://www.example.com/8zl4uj2/040_1913.jpg", 
#  "Max_v"  => "http://www.example.com/ta3w6rn/043_1914.jpg", 
#  "William_H" => "http://www.example.com/u43qn5h/046_1915.jpg", 
#  "William_L" => "http://www.example.com/n7gkk6e/049_1915.jpg", 
#  "Charles_G" => "http://www.example.com/2kxxroc/052_1917.jpg", 
#  "Max_P"  => "http://www.example.com/eyw7tm6/055_1918.jpg", 
#  "Johannes_S" => "http://www.example.com/gcjcv2p/058_1919.jpg", 
#  "Charles_É" => "http://www.example.com/nox3s6o/061_1920.jpg", 
#  "Nie"  => "http://www.example.com/mo9ga29/064_1922.jpg", 
#  "R"   => "http://www.example.com/kxq71if/067_1923.jpg", 
#  "Man"  => "http://www.example.com/2uwhw9y/070_1924.jpg", 
#  "Ja"   => "http://www.example.com/iwdavip/073_1925.jpg", 
#  "Gus"  => "http://www.example.com/73mbso2/076_1925.jpg", 
#  "Je"   => "http://www.example.com/rgugmas/079_1926.jpg", 
#  "Ar"   => "http://www.example.com/vy7is1v/082_1927.jpg", 
#  "O"   => "http://www.example.com/3jz5ve8/085_1928.jpg", 
#  "Lou"  => "http://www.example.com/srvj8d5/088_1929.jpg", 
#  "John"  => "http://www.example.com/7op2wb1/091_1929.jpg", 
#  "Chan"  => "http://www.example.com/1vqqwua/094_1930.jpg" 
# }