用於分組字彙詞的算法

Question

給定一組字詞，我們需要找到字彙詞並使用最佳算法單獨顯示每個類別。

輸入：

man car kile arc none like 

輸出：

man 
car arc 
kile like 
none 

我現在正在開發的最佳解決方案是基於一個哈希表，但我想公式字謎字轉換成整數值。

示例：man =>'m'+'a'+'n'但這不會給出唯一值。

有什麼建議嗎？

---

見在C＃下面的代碼：

string line = Console.ReadLine(); 
string []words=line.Split(' '); 
int[] numbers = GetUniqueInts(words); 
for (int i = 0; i < words.Length; i++) 
{ 
    if (table.ContainsKey(numbers[i])) 
    { 
     table[numbers[i]] = table[numbers[i]].Append(words[i]); 
    } 
    else 
    { 
     table.Add(numbers[i],new StringBuilder(words[i])); 
    } 

} 

的問題是如何發展GetUniqueInts(string [])方法。

Answer 1

根本不用打擾自定義散列函數。在任何平臺上使用正常的字符串散列函數。重要的是要讓你的哈希表的關鍵是「排序的詞」的概念 - 這個詞按字母排序，所以「car」=>「acr」。所有anagrams將具有相同的「排序詞」。

只需從「已排序的單詞」到「已排序單詞的單詞列表」進行散列即可。在LINQ這是非常容易的：

using System; 
using System.Collections.Generic; 
using System.Linq; 

class FindAnagrams 
{ 
    static void Main(string[] args) 
    { 
     var lookup = args.ToLookup(word => SortLetters(word)); 

     foreach (var entry in lookup) 
     { 
      foreach (var word in entry) 
      { 
       Console.Write(word); 
       Console.Write(" "); 
      } 
      Console.WriteLine(); 
     } 
    } 

    static string SortLetters(string original) 
    { 
     char[] letters = original.ToCharArray(); 
     Array.Sort(letters); 
     return new string(letters); 
    } 
} 

使用示例：

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like 
man 
car arc 
kile like 
none 

Answer 2

我不認爲你會發現比散列表具有自定義散列函數更好的功能（在散列函數之前將它的字母排序）。

這些字母的總和將永遠不起作用，因爲你不能真正使'ac'和'bb'不同。

Answer 3

您將需要大的整數（或實際上是一個位向量），但下面可能工作

每個字母GET分配的那封信的比特數的第一次出現，第二occurence得到位數爲信26. +

例如

＃1 = 1 b＃1 = 2 C＃1 = 4 ＃2 = 2^26 b＃2 = 2^27

然後，您可以將這些總和相加，以便根據字母獲取單詞的唯一值。

的字值的存儲要求是：

N * 26位

其中n是任意字母重複出現的最大數量。

Answer 4

一個Python版本的笑聲：

from collections import defaultdict 
res = defaultdict(list) 
L = "car, acr, bat, tab, get, cat".split(", ") 

for w in L: 
    res["".join(sorted(w))].append(w) 

print(res.values()) 

Answer 5

我與字母統計的簡單數組在此之前實施，例如：

unsigned char letter_frequency[26]; 

T母雞將它與每個詞一起存儲在數據庫表中。具有相同字母頻率「簽名」的單詞是anagrams，而簡單的SQL查詢則直接返回單詞的所有字母。

通過對一個非常大的詞典的一些實驗，我發現任何字母都沒有超過9的頻率計數，所以'簽名'可以表示爲一串數字0..9（大小可以是很容易通過以十六進制打包爲字節來減半，並且通過對數字進行二進制編碼而進一步減少，但是到目前爲止我沒有對此進行任何修改）。

這是一個紅寶石函數，用於計算給定單詞的簽名並將其存儲到哈希中，同時丟棄重複項。從散後來我建一個SQL表：

def processword(word, downcase) 
    word.chomp! 
    word.squeeze!(" ") 
    word.chomp!(" ") 
    if (downcase) 
    word.downcase! 
    end 
    if ($dict[word]==nil) 
    stdword=word.downcase 
    signature=$letters.collect {|letter| stdword.count(letter)} 
    signature.each do |cnt| 
     if (cnt>9) 
     puts "Signature overflow:#{word}|#{signature}|#{cnt}" 
     end 
    end 
    $dict[word]=[$wordid,signature] 
    $wordid=$wordid+1 
    end 
end 

Answer 6

我用了哥德爾靈感方案：

分配素數P_1至P_26的字母（以任意順序，但是要獲得短小的哈希值最好給普通字母小素數）。

在單詞中建立了字母的直方圖。

然後哈希值是每個字母的關聯素數提高到其頻率的乘積。這給每個字謎賦予了獨特的價值。

Python代碼：

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53] 


def get_frequency_map(word): 
    map = {} 

    for letter in word: 
     map[letter] = map.get(letter, 0) + 1 

    return map 


def hash(word): 
    map = get_frequency_map(word) 
    product = 1 
    for letter in map.iterkeys(): 
     product = product * primes[ord(letter)-97] ** map.get(letter, 0) 
    return product 

這巧妙地變換找到subanagrams到保理大量的（也被稱爲是棘手的）問題的棘手問題......

Answer 7

分配一個唯一的質數來字母az

迭代您的單詞數組，根據每個單詞中的字母創建素數的乘積。
將產品存儲在您的單詞列表中，並帶有相應的單詞。

對產品進行升序排列數組。

迭代陣列，在每次產品更改時執行control break。

Answer 8

在C中，我剛剛實現了下面的散列，它基本上做了一個26位掩碼，看字典中的單詞是否有特定的字母。所以，所有的anagrams都有相同的散列。哈希不考慮重複的字母，所以會有一些額外的重載，但它仍然比我的perl實現更快。

#define BUCKETS 49999 

struct bucket { 
    char *word; 
    struct bucket *next; 
}; 

static struct bucket hash_table[BUCKETS]; 

static unsigned int hash_word(char *word) 
{ 
    char *p = word; 
    unsigned int hash = 0; 

    while (*p) { 
     if (*p < 97 || *p > 122) { 
      return 0; 
     } 
     hash |= 2 << (*p - 97); 
     *p++; 
    } 

    return hash % BUCKETS; 
} 

重載的桶創建並添加爲鏈接列表等。然後編寫一個函數，確保匹配散列值的單詞長度相同，並且每個單詞中的字母都是1到1，並將其作爲匹配返回。

Answer 9

我將基於示例詞和其他字母我不會在意生成hasmap。

例如，如果一個詞是 「車」 我的哈希表會是這樣： 一，0 B，MAX C，1 d，MAX E，MAX ... .. r，2 。 因此任何有大於3將被視爲不匹配

（更多調整...） 而我的比較方法將比較哈希計算本身內的哈希總和。一旦它能夠識別單詞不相等，它就不會繼續。

public static HashMap<String, Integer> getHashMap(String word) { 
     HashMap<String, Integer> map = new HashMap<String, Integer>(); 
     String[] chars = word.split(""); 
     int index = 0; 
     for (String c : chars) { 
      map.put(c, index); 
      index++; 
     } 
     return map; 
    } 

    public static int alphaHash(String word, int base, 
      HashMap<String, Integer> map) { 
     String[] chars = word.split(""); 
     int result = 0; 
     for (String c : chars) { 
      if (c.length() <= 0 || c.equals(null)) { 
       continue; 
      } 
      int index = 0; 
      if (map.containsKey(c)) { 
       index = map.get(c); 
      } else { 
       index = Integer.MAX_VALUE; 
      } 
      result += index; 
      if (result > base) { 
       return result; 
      } 
     } 
     return result; 
    } 

主要方法

HashMap<String, Integer> map = getHashMap(sample); 
     int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map); 
     for (String s : args) { 
       if (sampleHash == alphaHash(s, sampleHash, map)) { 
        System.out.print(s + " "); 
       } 
      } 

Answer 10

，因爲它增加了額外的複雜性的查找，並增加了我不會使用散列。散列，排序和乘法運算都將比具有跟蹤唯一性的簡單基於陣列的直方圖解決方案慢。最壞的情況是O（2N）：

// structured for clarity 
static bool isAnagram(String s1, String s2) 
{ 
    int[] histogram = new int[256]; 

    int uniques = 0; 

    // scan first string 
    foreach (int c in s1) 
    { 
     // count occurrence 
     int count = ++histogram[c]; 

     // count uniques 
     if (count == 1) 
     { 
      ++uniques; 
     } 
    } 

    // scan second string 
    foreach (int c in s2) 
    { 
     // reverse count occurrence 
     int count = --histogram[c]; 

     // reverse count uniques 
     if (count == 0) 
     { 
      --uniques; 
     } 
     else if (count < 0) // trivial reject of longer strings or more occurrences 
     { 
      return false; 
     } 
    } 

    // final histogram unique count should be 0 
    return (uniques == 0); 
} 

Answer 11

字謎可通過以下方式找到：

1. 字的長度應匹配。
2. 根據整數值執行每個字符的添加。如果你在anagram上執行同樣的操作，這個數字將會匹配。
3. 按照整數值執行每個字符的乘法運算。如果您對anagram執行相同的操作，評估的值將匹配。

所以我想通過以上三個驗證，我們可以找到anagrams。如我錯了請糾正我。

---

實施例：兩個詞ABC CBA

長度是3。

薩姆對於這兩個詞的各個字符的是單個字符的兩個詞語294.

PROD是941094。

Answer 12

JavaScript版本。使用散列。

時間複雜度：0（nm）時，其中n是字的數，m是字的長度

var words = 'cat act mac tac ten cam net'.split(' '), 
    hashMap = {}; 

words.forEach(function(w){ 
    w = w.split('').sort().join(''); 
    hashMap[w] = (hashMap[w]|0) + 1; 
}); 

function print(obj,key){ 
    console.log(key, obj[key]); 
} 

Object.keys(hashMap).forEach(print.bind(null,hashMap)) 

Answer 13

只想除了添加簡單的python解決其他有用的答案：

def check_permutation_group(word_list): 
    result = {} 

    for word in word_list: 
     hash_arr_for_word = [0] * 128 # assuming standard ascii 

     for char in word: 
      char_int = ord(char) 
      hash_arr_for_word[char_int] += 1 

     hash_for_word = ''.join(str(item) for item in hash_arr_for_word) 

     if not result.get(hash_for_word, None): 
      result[str(hash_for_word)] = [word] 
     else: 
      result[str(hash_for_word)] += [word] 

return list(result.values()) 

Answer 14

Python代碼：

line = "man car kile arc none like" 
hmap = {} 
for w in line.split(): 
    ws = ''.join(sorted(w)) 
    try: 
    hmap[ws].append(w) 
    except KeyError: 
    hmap[ws] = [w] 

for i in hmap: 
    print hmap[i] 

輸出：

['car', 'arc'] 
['kile', 'like'] 
['none'] 
['man']