эффективный код рубина, чтобы найти самый короткий префикс для каждого слова, которое является уникальным среди слов

Question

У меня есть подобный хэш-таблица (но гораздо более крупный):

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

Быстрый тест два различных метода:

ось Х для размера входного массива хэша /, 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 

Как это работает?

• Сформировать всю возможную prefices, отображение их либо целое слово или :ambigous
• Реверс хэша и так prefices в порядке длиной обращенного хэш карты в кратчайшую приставку по убыванию
• Снять «слово» :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" 
# }