4

我在 GitHub 上搜索 Bloom Filters 时遇到了这个简单的 PHP 类，它被命名为“Bloom Filter”，但我认为它更像是一个“哈希表”，无论哪种方式我都很好奇，它很容易理解。

它读入一个单词文件并为每个单词创建一个哈希数组键，然后您可以检查该单词是否存在于哈希数组中。

我很好奇，尽管使用它与仅将实际单词存储为数组键或值然后检查该单词是否存在于数组中相比有什么好处，理论上这只会增加开销并做同样的事情，请帮助我明白我错过了什么吗？

<?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) {
    // ...

（PS：这段代码不会像预期的那样工作，因为每个单词都会包含换行符，所以你需要先去掉它。但我希望你明白。）

于 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 回答