algorithm - 名前と住所のデータから ID を作成します。ハッシュ/ダイジェスト

Question

私の問題：

人の名前と住所をエンコードされた ID として表す方法を探しています。id には英数字のみを使用し、衝突を防止し、できるだけ少ない文字数で表す必要があります。私が最初に考えたのは、単純に MD5 や SHA1 などの暗号化ハッシュ関数を使用することでしたが、これはやり過ぎのように思え (セキュリティは重要ではなく、一方向である必要はありません)、短いID。この問題に適合する既存のアルゴリズムを知っている人はいますか?

つまり、次の関数を実装して、同じ入力に対して一貫して同じ値を返し、衝突の可能性が低く、id が 20 文字未満になるようにする最善の方法は何ですか?

>>> make_fake_id(fname = 'Oscar', lname = 'Grouch', stnum = '1', stname = 'Sesame', zip = '12345')
N1743123734

アプリケーションのコンテキスト (興味のある方):

これは、レコード連携アプリに使用されます。入力された名前と住所を指定すると、非常に大きなデータベースを検索して最も一致するものを探し、データベース ID とその他のデータを返します (これを行う方法はここでは重要ではありません)。一致するものがない場合は、検索入力 (エンティティの名前と住所のデータ) からこの疑似/生成/派生 ID を生成する必要があります。すべての検索レコードは、実際の (一致/リンクから得られる実際のデータベース ID) またはこの生成された疑似/生成/派生 ID のいずれかを持つ出力レコードになるはずです。疑似 ID には、実際の ID と区別するために文字 (N など) がプレフィックスとして付けられます。

score 5 · Accepted Answer

あなたが MD5 と SHA1 にノーと言ったのは知っていますが、いずれにせよ検討すべきだと思います。十分に研究されたハッシュアルゴリズムであるだけでなく、この長さにより衝突の可能性に対する保護が強化されます。衝突に強いハッシュはありませんが、一般的に、暗号化されたハッシュは、自分で思いつくものよりも衝突しにくいものです。

score 3 · Accepted Answer

他の品質ではなく、衝突耐性のために暗号化ハッシュを使用します
ハッシュから必要な数のバイトを使用 (切り捨て)
英数字に変換
ハッシュの代わりに英数字の文字列を切り捨てることもできます

これを行う簡単な方法: データをハッシュし、base64 でエンコードし、英数字以外の文字をすべて削除し、切り捨てます。

N_HASH_CHARS = 11
import hashlib, re
def digest(name, address):
  hash = hashlib.md5(name + "|" + address).digest().encode("base64")
  alnum_hash = re.sub(r'[^a-zA-Z0-9]', "", hash)
  return alnum_hash[:N_HASH_CHARS]

何文字の英数字を保持する必要がありますか? 各文字は、約 5.95 ビットのエントロピー (log(62,2)) を提供します。11 文字で 65.5 ビットのエントロピーが得られます。これは、最初の 2**32.7 ユーザー (約 70 億) の衝突を回避するのに十分なはずです。

score 0 · Accepted Answer

これらのIDをユーザーに「割り当てる」つもりかどうか疑問に思いますか？もしそうなら、私はあなたのユーザーがあなたが提案するものを嫌うことを期待します。「AAAAA01」のユーザーIDが必要なのは誰ですか？

したがって、これらのIDがユーザーに表示される場合は、ユーザーに好きなものを選択させて、一意性（簡単）を確認する必要があります。それらがユーザーに表示されない場合（たとえば、内部主キー）、OracleSequenceやSQLServer AutoNumberなどの適切な手法を使用して順番に生成します（これも簡単です）。

これらのIDが複数回登録しているユーザーを検出する試みである場合は、暗号化ハッシュとそれに続く登録データ（名前、住所など）の完全な比較を検討する必要があることに同意します。ただし、使用可能にするには、ハッシュを計算したり比較したりする前に、データを標準形式（標準化された大文字小文字、空白、標準の番地など）に変換する必要があります。そうしないと、些細な違いに基づいて不一致になります。

編集：あなたの編集に基づいて問題空間をよりよく理解したので、あなたのアルゴリズムが（これまでのところ）ほとんどの一致をキャッチする可能性は非常に低いと思います。入力を正規化するという私の提案を超えて、単一の一致でのオールオアナッシングの試みではなく、少数の可能な一致のランク付けされたリスト（可能であれば人間によって解決される）をもたらすアプローチを検討することをお勧めします。つまり、ルックアップアプローチではなく検索アプローチをお勧めします。

それはあなたの状況で実行可能ですか？

score 0 · Accepted Answer

良い解決策は、アプリケーションによって多少異なります。ユーザーの数とすべてのユーザーのセットを知っていますか？あなたがより多くの詳細を提供するならば、あなたはより良い助けを得るでしょう。

score 0 · Accepted Answer

シリアル番号を示唆している他のポスターに同意します。OTOH、あなたが本当に、本当に本当に何か他のことをしたいのなら：

データから SHA1 ハッシュを作成し、シリアル番号フィールドを含むテーブルに格納します。

次に、データを取得したら、ハッシュを計算し、テーブルで検索して、シリアルを取得します。それがあなたの ID です。テーブルにない場合は、挿入します。

score -1 · Accepted Answer

同じ名前で同じ住所に複数の人がいる場合は、ここで乾杯します (これを検出するためのコードを追加せず、何らかの種類の識別子を追加します)。

しかし、問題がないと仮定すると、完全な住所の番地と郵便番号の部分で十分に一意性が保証されるため、名前から十分なデータを追加することで問題を解決できます...

各アドレスのキー値を生成および維持できるデータベースまたはその他の永続化メカニズムにアクセスできますか? 次に、住所と個々のエンティティを 2 つのキー付きディクショナリ構造に保持します。キーは、新しい個別の住所、遭遇した人ごとに自動生成されます...そして、自動生成された英数字キーを使用します...

You could use AAAAA01  for first person at first address,
              AAAAA02 for second person at first address,
              AAAAB07 for the seventh resident at the second adresss, etc.

これらのエンティティキーマッピングを生成および維持する方法がない場合は、完全な住所/Zip および fullNAme、または同じもののハッシュ値を使用する必要がありますが、ハッシュ値アプローチでは重複が生成される可能性がほとんどありません。 ..

algorithm - 名前と住所のデータから ID を作成します。ハッシュ/ダイジェスト

6 に答える 6

Related

Reference