algorithm - アナグラム単語をグループ化するためのアルゴリズム

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 [])です。

score 39 · Accepted Answer

カスタムハッシュ関数をまったく気にしないでください。プラットフォームが何であれ、通常の文字列ハッシュ関数を使用してください。重要なことは、ハッシュテーブルのキーを「ソートされた単語」のアイデアにすることです。単語は文字でソートされるため、「car」=>「acr」になります。すべてのアナグラムは、同じ「ソートされた単語」を持ちます。

「ソートされた単語」から「そのソートされた単語の単語のリスト」へのハッシュを作成するだけです。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

score 19 · Accepted Answer

私はゲーデルにインスパイアされたスキームを使用しました：

素数 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

これは、サブアナグラムを見つけるというトリッキーな問題を、(トリッキーなことでも知られている) 大きな数を因数分解するという問題に巧みに変換します...

score 7 · Accepted Answer

笑いのための 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())

score 3 · Accepted Answer

カスタムハッシュ関数（ハッシュする前に単語の文字を並べ替える）を備えたハッシュテーブルよりも優れたものはないと思います。

'ac'と'bb'を実際に区別することはできないため、文字の合計は機能しません。

score 3 · Accepted Answer

大きな整数（または実際にはビットベクトル）が必要になりますが、次の方法でうまくいくかもしれません

各文字が最初に出現すると、その文字のビット番号が割り当てられ、2 番目に出現すると、その文字のビット番号 + 26 が取得されます。

例えば

a #1 = 1 b #1 = 2 c #1 = 4 a #2 = 2^26 b #2 = 2 ^ 27

次に、これらを合計して、文字に基づいて単語の一意の値を取得できます。

ワード値のストレージ要件は次のとおりです。

n * 26 ビット

ここで、n は繰り返される文字の最大出現回数です。

score 2 · Accepted Answer

ハッシュはルックアップと追加の複雑さを増すため、使用しません。ハッシュ、並べ替え、乗算はすべて、一意を追跡する単純な配列ベースのヒストグラムソリューションよりも遅くなります。最悪の場合は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);
}

score 1 · Accepted Answer

私は以前に文字数の単純な配列でこれを実装しました。

unsigned char letter_frequency[26];

次に、それを各単語とともにデータベーステーブルに格納します。同じ文字頻度「署名」を持つ単語はアナグラムであり、単純な SQL クエリは単語のすべてのアナグラムを直接返します。

非常に大きな辞書を使ったいくつかの実験では、どの文字でも頻度カウント 9 を超える単語は見つからなかったので、「署名」は数字 0..9 の文字列として表すことができます (サイズはパッキングによって簡単に半分にすることができます)。 16 進数としてバイトに変換し、数値をバイナリエンコードすることでさらに削減しましたが、これまでのところ気にしませんでした)。

これは、指定された単語の署名を計算してハッシュに格納し、重複を破棄するルビ関数です。ハッシュから、後で 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

score 1 · Accepted Answer

文字 a ～ z に一意の素数を割り当てる

単語配列を繰り返し、各単語の文字に基づいて素数の積を作成します。
その製品を、対応する単語とともに単語リストに保存します。

配列を積の昇順で並べ替えます。

製品が変更されるたびにコントロールブレークを実行して、配列を反復します。

score 0 · Accepted Answer

Cでは、次のハッシュを実装しました。これは、辞書内の単語に特定の文字が含まれているかどうかについて、基本的に26ビットのビットマスクを実行します。したがって、すべてのアナグラムは同じハッシュを持ちます。ハッシュは繰り返される文字を考慮に入れていないため、追加のオーバーロードが発生しますが、それでも私の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であることを確認し、それを一致として返す関数を記述します。

score 0 · Accepted Answer

サンプルの単語と、気にしない残りのアルファベットに基づいて hasmap を生成します。

たとえば、単語が「車」の場合、ハッシュテーブルは次のようになります: a,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 + " ");
                }
            }

score 0 · Accepted Answer

アナグラムは、次の方法で見つけることができます。

単語の長さは一致する必要があります。
各文字の加算を整数値で行います。この合計は、アナグラムで同じことを実行すると一致します。
整数値に関して各文字の乗算を実行します。アナグラムで同じことをすると、評価値が一致します。

上記の 3 つの検証を通じて、アナグラムを見つけることができると考えました。私が間違っている場合は修正してください。

例: abc cba

両方の単語の長さは 3 です。

両方の単語の個々の文字の合計は 294 です。

両方の単語の個々の文字の製品は 941094 です。

score 0 · Accepted Answer

他の有用な回答に加えて、単純な 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())

score -1 · Accepted Answer

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

algorithm - アナグラム単語をグループ化するためのアルゴリズム

14 に答える 14

Related

Reference