Class: Searcher

Inherits:
Object
  • Object
show all
Defined in:
lib/igo/trie.rb

Overview

DoubleArray検索用のクラス

Instance Method Summary collapse

Constructor Details

#initialize(path) ⇒ Searcher

保存されているDoubleArrayを読み込んで、このクラスのインスタンスを作成する

path

DoubleArrayが保存されているファイルのパス



101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/igo/trie.rb', line 101

def initialize(path)
  fmis = FileMappedInputStream.new(path)
  node_size = fmis.get_int()
  tind_size = fmis.get_int()
  tail_size = fmis.get_int()
  @key_set_size = tind_size
  @begs = fmis.get_int_array(tind_size)
  @base = fmis.get_int_array(node_size)
  @lens = fmis.get_short_array(tind_size)
  @chck = fmis.get_char_array(node_size)
  @tail = fmis.get_string(tail_size)
  fmis.close
end

Instance Method Details

#each_common_prefix(key, start, callback) ⇒ Object

common-prefix検索を行う

  • 条件に一致するキーが見つかる度に、callback.callメソッドが呼び出される

key

検索対象のキー文字列

start

検索対象となるキー文字列の最初の添字

callback

一致を検出した場合に呼び出されるコールバックメソッド



151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/igo/trie.rb', line 151

def each_common_prefix(key, start, callback)
  base = @base
  chck = @chck
  node = @base[0]
  offset = -1
  kin = KeyStream.new(key, start)
  
  while true
    code = kin.read
    offset += 1
    terminal_index = node
    
    if(chck[terminal_index] == Node::Chck::TERMINATE_CODE)
      callback.call(start, offset, Node::Base.ids(base[terminal_index]))
      
      if(code == Node::Chck::TERMINATE_CODE)
        return
      end
    end
    
    idx = node + code
    node = base[idx]
    
    if(chck[idx] == code)
      if(node >= 0)
        next
      else
        call_if_key_including(kin, node, start, offset, callback)
      end
    end
    return
  end
end

#search(key) ⇒ Object

キーを検索する

key

検索対象のキー文字列

return

キーが見つかった場合はそのIDを、見つからなかった場合は-1を返す



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/igo/trie.rb', line 124

def search(key)
  base = @base
  chck = @chck
  node = @base[0]
  kin = KeyStream.new(key)
  
  while true
    code = kin.read
    idx = node + code
    node = base[idx]
    
    if(chck[idx] == code)
      if(node >= 0)
        next
      elsif(kin.eos? or key_exists?(kin, node))
        return Node::Base.ids(node)
      end
      return -1
    end
  end
end

#size ⇒ Object

DoubleArrayに格納されているキーの数を返却

return

DoubleArrayに格納されているキーの数



117
118
119
 
# File 'lib/igo/trie.rb', line 117

def size
  return @key_set_size
end