2

重複の可能性：
Pythonで一意の短縮URLを作成するにはどうすればよいですか？

ディスク上のファイルへのパスを固定長の文字列に本質的に短縮して、絶対パスまたはこのエイリアスを介してアクセスできるようにする方法を探しています。

エイリアスを持つすべてのパスを持つ辞書のキーとしてUUIDを使用することを検討してきましたが、長すぎることがわかったため、5〜10文字にします。また、ハッシュを調べて、実際のパスをエイリアスとして直接使用できる有用な文字列にハッシュして、値をディスク上のテーブルに格納することを考えました。私はハッシュの分野で非常に新鮮ですが、私が理解しているように、パスを再ハッシュするだけでキーを取得でき、キーをテーブルに入力すると、メモリに完全にロードしなくても値が得られますまたはディスクから完全に読み取ります。

最終的な目標は、私のカスタムブラウザで、次を使用して同じファイルを指すことができるようにすることです。

"/root/folder1/folder2/folder3/file.png" and e.g. "MTEzNDUy"

可能な辞書は次のようになります。固定長のキーに注意してください。

{"MSFjak5m": "/root/folder1/folder2/file.png",
"sofkAkfg": "/root/file.exe",
"ASg5OFA3": "/root/file2.so",
"fFAgeEGH": "/root/file5.so"}

ディスク上にルックアップテーブルがあることは許容されますが、パスをそのようなエイリアスに単純に圧縮できれば、さらに良いでしょう。最善の解決策は、キーと値のペアを格納する必要があるのではなく、テーブルがハッシュを直接使用して値を検索できるようにすることです。これは、エイリアスを取得するために1つのハッシュを実行してから、値を見つけるためにそのキーに基づいてさらに別のハッシュを実行する辞書..私が間違っている場合は私を訂正してください。

エントリの数は約100000であり、すべての操作はPythonで保持することが望ましいでしょう。

ありがとう

編集
MD5ハッシュをエンコードし、結果の一部をキーとして使用して、いくつかのテストを実行しました。最初の4文字を使用すると、600エントリごとに約1の衝突率が得られることがわかりました。最初の5つを使用すると、1/4000の衝突率が得られました。

これらのエントリは、通常の操作では1日あたり約5のレートで、ピーク時は1日あたり最大100のレートで一度に作成され、最大1000000エントリを超えることはありません。

これを考慮すると、取得したハッシュの一意性を、すでに保存されているものと比較して確認し、次のいずれかで処理する可能性があります。A：パスを作成できないため、ユーザーに警告する必要があります。別の名前を選択するか、B：一意のハッシュが見つかるまでハッシュで許可される文字数を増やします。現時点では、どちらも許容できるようです。

（補足、ハッシュ関数を使用する目的を破って、保存されたハッシュテーブルに対してハッシュをチェックしていますか？）

Windowsでのテストのコード。フォルダに対してのみテストすると、ドライブに約50000があります。

import hashlib
from random import shuffle

def shuffle_string(word):
    word = list(word)
    shuffle(word)
    return ''.join(word)

tests = 10
chars = 5
_entries = 0
_hashes = {}
for test in xrange(tests):
    for path, _d, _f in os.walk('c:/'):

        unique_path = "%s%i" % (path, test)
        key = hashlib.md5(unique_path).digest().encode('base64').strip()[:chars]
        _hashes[key] = unique_path
        _entries += 1

total_collisions = _entries-len(_hashes)

print "%s Entries \nTests: %s\nChars: %s" % (_entries, tests, chars)
if total_collisions:
    average_collisions = total_collisions / float(tests)
    odds = _entries / float(average_collisions)
    print "%s collisions per %s entries" % (average_collisions, _entries)
    print "odds: 1 in %s" % odds

    if odds: 
        print "chance: %s%%" % (1 / (_entries / float(average_collisions)))
else:
    print "No collisions occured"
4

1 に答える 1

1

hashlib標準モジュールを使用して文字列のハッシュを計算し、のペアをに格納することを検討し{hash: string}てくださいdict。

于 2012-11-28T12:03:04.460 に答える