Class: Igo::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が保存されているファイルのパス



110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/igo/trie.rb', line 110

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

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



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/igo/trie.rb', line 160

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を返す



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/igo/trie.rb', line 133

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に格納されているキーの数



126
127
128
 
# File 'lib/igo/trie.rb', line 126

def size
  return @key_set_size
end