言葉

Question

の中で一意である各単語のための最短のプレフィックスを見つけるための効率的なRubyコード私は似たハッシュテーブル（しかし、はるかに大きなもの）を持っている：

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" 
} 

私は効率的で最短のプレフィックスを見つけたいです接頭辞が与えられたキーの中で一意である各キーのための方法。言い換えれば、短い接頭辞を持つことで、各行はハッシュテーブルでも認識可能です。このハッシュテーブルの場合、まだ認識ラインを作る最短プレフィックス：

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" 
} 

私の最初の試みは、各キーまたは単語のための最短のプレフィックスを見つけるために：

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]] 
}; 

アルゴリズムとコードが最適にはほど遠いです、実際、高速のマシンであっても実際には遅く、ハッシュテーブルがはるかに大きくなると使用できなくなります。

例ハッシュをフェッチすることができる：

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

つの異なる方法の迅速なベンチマーク：X軸は入力ハッシュ/配列、Y-の大きさのためである

軸は、実行時間（秒）です。

最終的なコード、空腹今最速とないので、メモリは：

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

は、この作業を行いどのようなアルゴリズム

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 

のですか？

• は、ハッシュをリバース単語全体または:ambigous
• のいずれかにマッピング、すべての可能なpreficesを生成し、preficesは逆のハッシュは最短の接頭辞にマップされた長さの降順にあるので
• 削除します"word" :ambigous逆のハッシュから

Answer 2

あなたは明確な略語のリストを生成するためにAbbrev.abbrevを使用することができます。キーと省略語をキーとしてハッシュを生成するので、最短の略語を最初に抽出し、キーと値を入れ替える必要があります。ここで

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" 
# }