質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.04%

RubyでBloomfilter実装

受付中

回答 0

投稿

  • 評価
  • クリップ 0
  • VIEW 871

score 8

前提・実現したいこと

rubyを用いて、bloomfilterの機能が搭載されている検索システムを作っています。
bloomfilterには適当な英単語を十数個登録してビット値として配列に格納します。そして検索機能を設置し、入力された英単語が登録された英単語にあるならpositiveを、ないならnegativeを返すように作ります。

発生している問題・エラーメッセージ

bloomfilterの配列に格納されている値と、検索した文字列の値が食い違い、Negativeになってしまいます。(False negativeが発生する)
例(実際にコードを走らせて見た場合))
Snowstorm, Downpour, Rainstorm, Blusterous, Lightning, Sleety, Hail, Sunny, Cloudy, //bloomfilterに登録されている英単語
11011010100010101111001000101101 //bloomfilterの配列
Weather Search
search: s hoge|終了(exit): e
コマンドs Snowstorm
search
s Snowstorm
25
5
16
index:    11011010100010101111001000101101
KEYS:    00000100000000001000000001000000 //登録してある単語で検索すると、何故か入ってない場所にビットが立つ
i: 25 -> 0|1i: 5 -> 0|1i: 16 -> 1|1

該当のソースコード

# coding: utf-8
require 'digest'
#Digest::MD5.haexdigest('hoge').to_s

SIZE = 32
BFINDEX = Array.new(SIZE){0}
S = [13, 211, 928]


def hash(obj)
    h = Array.new(3){0};

    S.length.times do |i|
        tmp = 0
        md5 = Digest::MD5.hexdigest(obj.to_s + S[i].to_s).unpack("B*")

        md5.to_s.each_char.with_index { |c, i|
            if c.to_i == 1 then
                 tmp+=1
            end
        }
        h[i] = (tmp + S[i]) % SIZE
    end

    return h
end

# Bloom Filter
def reg(obj)
    keys = hash(obj).flatten

    keys.each do |key|
        BFINDEX[key] = 1
    end
end




def search(obj)
    puts obj
    key = hash(obj) #.flatten
    filter = 0

    tmp = Array.new(SIZE){0}

    puts key

    key.each do |k|
        tmp[k] = 1
    end

    print("index:    ", BFINDEX.join(""), "\nKEYS:    ", tmp.join(""), "\n")

    key.each do |i|
        print("i: ", i, " -> ",BFINDEX[i] , "|",tmp[i])
        if BFINDEX[i] != 0 then
            filter = filter + 1
        end
    end

    if filter == 3
        print("\npositive\n\n")
    else
        print("\nnegative\n\n")
    end
end




# Main

words = ["Snowstorm","Downpour","Rainstorm","Blusterous","Lightning","Sleety","Hail","Sunny","Cloudy"]


words.each do |cats|
    print(cats, ", ")
    reg(cats)

end

puts

print(BFINDEX.join(""), "\n")

begin

while true
    puts "Weather Search"
    puts "search: s hoge|終了(exit): e"
    print("コマンド")
    num = gets.chomp

    case num

    when /s /
        puts "search"
        x = num.split('search ')
        search(x)
    when 'e'
        break
    end
end

rescue Interrupt
    exit()
end

試したこと

ハッシュ値を変えたり、ハッシュ関数そのものを変える、rubyのバージョンを変えるなど試みてみましたが同様の問題が発生します。
ハッシュ値は3つのつもりで作ってましたが、4つでも5つでも同様のエラーが起こるので取り敢えず原因を知りたく思い、皆様の知恵をお借りしたく思います。

補足情報(言語/FW/ツール等のバージョンなど)

VMware Workstation 12 playerを使用し、ubuntu 64bitの仮想環境でターミナルを用いて実行・制作しています
ruby2.2.2です。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.04%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る