4

ブルームフィルターを検索しているときにGitHubでこの単純なPHPクラスに出くわしました。これは「ブルームフィルター」という名前でしたが、どちらにしても「ハッシュテーブル」のようなものだと思います。理解するのは非常に簡単です。

単語のファイルを読み取り、単語ごとにハッシュ配列キーを作成します。次に、単語がハッシュ配列に存在するかどうかを確認できます。

実際の単語を配列のキーまたは値として保存し、その単語が配列に存在するかどうかを確認するのではなく、これを使用することの利点はありますか？理論的には、これはオーバーヘッドを追加して同じことを行うだけです。助けてください私は私が欠けているものを理解していますか？

<?php
class Dictionary {
    private $words;
    private $wordsHash;
    public $hashLength;

    public function __construct($filepath, $hashLength) {
        $this->words = file($filepath);
        $this->hashLength = $hashLength;
        foreach($this->words as $word){
            $this->wordsHash[$this->createHash($word)] = true;
        }
        echo 'words: ' . count($this->words) . '   hashes: ' . count($this->wordsHash) . "\n";
    }

    public function createHash($str){
        $hash = substr(md5(trim($str)), 0, $this->hashLength);
        return $hash;
    }

    public function checkDictionary($str){
        $hash = $this->createHash(trim($str));
        if(array_key_exists ($hash , $this->wordsHash)){
            return true;
        }
        return false;
    }

}
?>

dictionary.txtファイルには10,000語が含まれていますが、デモ用にいくつか表示します

der
die
und
in
den
von
zu
das
mit
sich
des
auf
für
ist

使用例： 

<?php
$dictionary = new Dictionary('dictionary.txt', 30);

if($dictionary->checkDictionary('den')){
    echo 'The Word den Exist in the Hash Table';
}else{
    echo 'The Word den DOES NOT Exist in the Hash Table';
}
?>
4

4 に答える 4

6

これに関する考え方は、キーの検索は配列内の特定の値の検索よりもはるかに高速であるように思われます。これは、非常に大きなアレイに特に当てはまります。ただし、（すでに述べたように）オーバーヘッドと衝突を回避するためのより簡単なアプローチをお勧めします。

$words = array_flip( file($filename) );

// The actual values are now the keys!
// So checking for a word works like this:
if (isset($words['und'])) {
    // ...

// Travling through the words works like this:
foreach ($words as $word => $i) {
    // ...

（追記：すべての単語に改行が含まれているため、このコードは期待どおりに機能しません。そのため、最初に改行を削除する必要があります。ただし、アイデアが得られることを願っています。）

于 2012-05-03T20:19:20.733 に答える
3

この種のアプローチは、通常、非常に大きな文字列を使用して行われます。ギャラリーを作成するときにこの方法を使用したことがあります。アップロードされたファイルにはsha1、ファイル全体のチェックサムに基づいて名前が付けられます（実際の名前はデータベースに保存されます）。このように、重複ファイルがアップロードされた場合、それは簡単に拒否されます。

彼が3文字の文字列（さらに言えば50文字の文字列）をハッシュすることでどのようなメリットが得られるのか正確にはわかりません。私はそのようにはしません。元の開発者に質問する必要があります。

于 2012-05-03T20:18:50.563 に答える
2

githubで見つけた場合は、見つけたコードの作成者に尋ねる価値があります。

辞書クラスには2つの利点があります。キーをトリミングし、重複を回避しますが、次のコードはほとんど同等であり、はるかに高速になる可能性があります。

$words = file($filepath);
$words = array_map('trim', $words);
$words = array_unique($words);
sort($words); // just for convenience debugging

...

if (in_array($test, $words)) {
    return true;
} else {
    return false;
}

疑わしい場合は、競合する各手法（または任意の手法）のベンチマークを行うことで、特定のユースケースに最適なソリューションを明確に示す必要があります。

于 2012-05-03T20:22:30.527 に答える
2

そのコンストラクターと、単語自体をキーとして使用することの間に、機能的な違いはありません。数値以外のphpの配列は、基本的にハッシュマップです（正しく思い出せば、構文と実装では）。このスニペットを検討してください。

$contents = file($filepath);
$dictionary = array();
foreach($contents as $word) {
    $dictionary[$word] = $word;
}

if(array_key_exists('den', $dictionary){
    echo 'The Word den Exist in the Hash Table';
}else{
    echo 'The Word den DOES NOT Exist in the Hash Table';
}

サンプルクラスと同じことをします。失うのは->構文だけですが、技術的$dictionary['den']には存在条件として使用できます...設定されていない場合はnullを返し、falseと評価されるため...

このクラスはまた、暗号化されたセキュリティが必要とされない場合に、暗号化されたハッシュ関数を使用することのないコンピュータサイエンスをコミットします。MD5アルゴリズムは、通常の非セキュア（比較的、この時点ではMD5セキュアの呼び出しは疑わしい）ハッシュ関数よりも実行にはるかにコストがかかります。辞書クラスの使用は、実際には何も提供しないことに加えて、大幅に遅くなります。Truthが指摘しているように、非常に長い文字列のダイジェストを比較すると、時間を節約できます。しかし、ダイジェストの計算には依然としてコストがかかり、3文字の文字列のダイジェストの計算は時間の無駄に他なりません。

于 2012-05-03T20:32:58.743 に答える