6

私はたくさんの名前を持っています（数百万）。それぞれに、名、オプションのミドルネーム、および姓があります。これらの名前を、名前を一意に表す番号にエンコードする必要があります。エンコーディングは1対1である必要があります。つまり、名前は1つの番号にのみ関連付けられ、番号は1つの名前にのみ関連付けられる必要があります。

これをエンコードするスマートな方法は何ですか？アルファベットセット内の位置（a-> 1、b-> 2 ..など）に従って名前の各アルファベットにタグを付けるのは簡単なので、Deepaのような名前は-> 455161になりますが、これもここでは、「16」が本当に16なのか、1と6の組み合わせなのかわかりません。

だから、私は名前をエンコードするスマートな方法を探しています。

さらに、任意の名前の出力数値の桁数が固定桁数になるようにエンコードする必要があります。つまり、長さに依存しないようにする必要があります。これは可能ですか？

ありがとうAbhishekS

4

6 に答える 6

9

同じ幅の数字を得るには、左側をゼロパッドするだけではいけませんか？

いくつかのオプション：

  1. それらを並べ替えます。それらを数える。10番目の名前は10番です。
  2. 各文字を、26（大文字と小文字を区別しない、数字なし）または52（大文字と小文字を区別しない、数字なし）または36（大文字と小文字を区別しない）または62（大文字と小文字を区別する）の数字の数字として扱います。intの値を計算します。たとえば、「abc」という名前の場合、0 * 26 ^ 2 + 1 * 26 ^ 1 + 2 * 20^0になります。中国の名前では、調性を示すために数字を使用する場合があります。
  3. 「完全なハッシュ」スキームを使用する：http：//en.wikipedia.org/wiki/Perfect_hash_function
  4. これは主に楽しみの中で提案されています：ゲーデル数を使用してください:)。したがって、「abc」は2 ^ 0 * 3 ^ 1 * 5^2-になります。これは素数の累乗の積です。数を因数分解すると、文字が返されます。ただし、その数はかなり大きくなる可能性があります。
  5. まだ使用していない場合は、ASCIIに変換します。次に、文字の各序数を基数256の記数法の数字として扱います。したがって、「abc」は0 * 256 ^ 2 + 1 * 256 ^ 1 + 2 * 256^0です。

名前と番号のリストを時々更新できるようにする必要がある場合は、＃2、＃4、および＃5が機能するはずです。＃1と＃3には問題があります。＃5はおそらく最も将来性がありますが、ある時点でユニコードが必要になる場合があります。

2 ^ 8==256の代わりに2^32の累乗を使用して、＃5のバリアントとしてUnicodeを実行できると思います。

于 2012-04-26T19:50:48.057 に答える
3

そこでやろうとしているのは、実際にはハッシュです（少なくとも桁数が固定されている場合）。衝突がほとんどない優れたハッシュアルゴリズムがいくつかあります。たとえば、sha1を試してみてください。これは、十分にテストされており、現代語で利用できます（http://en.wikipedia.org/wiki/Sha1を参照）。gitには十分なようですので、うまくいく可能性があります。

もちろん、2つの異なる名前に対して同一のハッシュ値が存在する可能性はわずかですが、ハッシュの場合は常にそうであり、対処することができます。sha1などを使用すると、名前とIDの間に明確な関係がなくなります。これは、問題に応じて、良いことも悪いこともあります。

本当に一意のIDが必要な場合は、NealBが提案するようなことを行い、自分でIDを作成し、データベース内の名前とIDを接続する必要があります（ランダムに作成して衝突をチェックするか、0000000000001から開始して増分することができます） 。

（いくつか考えて最初のコメントを読んだ後の改善された答え）

于 2012-04-26T17:51:16.823 に答える
2

BigInteger次のように任意の文字列をエンコードするためにを使用できます。

BigInteger bi = new BigInteger("some string".getBytes());

文字列を元に戻すには、次を使用します。

String str = new String(bi.toByteArray());
于 2016-12-01T14:40:09.583 に答える
1

https://en.wikipedia.org/wiki/Huffman_codingをご覧ください。それが標準的なアプローチです。

于 2012-04-26T18:01:59.077 に答える
1

私はあなたが提案したものと非常によく似た問題の解決策を探していました、そしてこれは私が思いついたものです：

def hash_string(value):
    score = 0
    depth = 1
    for char in value:
        score += (ord(char)) * depth
        depth /= 256.
    return score

Pythonに慣れていない場合は、次のようになります。

  1. スコアは最初は0で、深さは1に設定されています
  2. ordすべての文字について、値*深さ を追加します
    1. このord関数は、各文字のUTF-8値（0〜255）を返します。
    2. 次に、「深さ」を掛けます。
  3. 最後に、深さは256で除算されます。

基本的に、それが機能する方法は、最初の文字がスコアに追加する一方で、後の文字はますます貢献しないというものです。整数が必要な場合は、終了スコアに2**64を掛けます。それ以外の場合は、0〜256の10進値になります。このエンコード方式はバイナリデータに対して機能し、バイト/文字には256個の可能な値しかありません。

この方法は、小さい文字列値には最適ですが、長い文字列の場合、10進値には通常の倍精度（64ビット）よりも高い精度が必要であることに気付くでしょう。Javaでは「BigDecimal」を使用でき、Pythonでは「decimal」モジュールを使用して精度を高めます。このメソッドを使用する利点は、返される値がソートされた順序であるため、「効率的に」検索できることです。

于 2013-01-30T06:14:50.357 に答える
0

すべての文字（および少なくとも空白）が位置を占める場合は、それを翻訳できます。

したがって、ABCは1,2,3であり、次のように変換する必要があります。

1*(2*26+1)² + 2*(53) + 3

このようにして、任意の文字列をエンコードできますが、入力の長さが制限されていない場合（およびどのようにすべきですか？）、長さの上限があるとは限りません。

于 2012-04-26T18:01:49.117 に答える