# コード例１：Trie木の例（書きかけ）
class Node:
def __init__(self, left=-1, right=-1, ch='', word_id=-1):
self.left = left
self.right = right
self.ch = ch
self.word_id = word_id
class Trie:
def __init__(self):
self.data = dict()
self.data[0] = Node()
# その他、登録メソッドとか検索メソッドとか...
# コード例２：Wikipediaタイトルを加工して見出し語リストを作る
# 元ファイルはこちら：https://dumps.wikimedia.org/jawiki/latest/jawiki-latest-all-titles-in-ns0.gz
import gzip
with gzip.open('jawiki-latest-all-titles-in-ns0.gz', 'r') as f:
with open('words.txt', 'w', encoding='utf-8') as fout:
for ln in f:
w = ln.decode('utf-8').strip()
if len(w) >= 2:
print(w, file=fout)
# コード例３：簡単にdouble arrayを作ってみたい
import sys
from collections import defaultdict
import random
import time
def get_branch_db(words):
'''
分岐データベースの準備
（先頭からの部分文字列の文字IDのtuple => 次に来る文字の文字IDのset）
同時に文字テーブルとその逆引きも作っておく
'''
db = defaultdict(set) # 分岐データベース
db_keys = [] # ordered defaultdictにしたいのでこのようにする
db_keys_set = set() # db_keysの作成補助
cs = [''] # 文字テーブル
c2code = {'':0} # 文字テーブル逆引き辞書
for word in words[1:]: # 先頭は空文字列なので省く
for i in range(len(word)+1):
pre = word[:i]
c = word[i] if i < len(word) else ''
if c in c2code:
code = c2code[c]
else:
cs.append(c)
code = len(c2code)
c2code[c] = code
pre_codes = tuple(c2code[c] for c in pre)
db[pre_codes].add(code)
if not pre_codes in db_keys_set:
db_keys.append(pre_codes)
db_keys_set.add(pre_codes)
return dict(db), db_keys, cs, c2code
def get_base_s(s, v, check, slot_start=1):
'''
現在のノード位置:s, 次の文字IDのset:v, check配列:checkを入力して、
空きスロットを左から探してbase[s]を求める
'''
min_v = min(v)
offsets = [vn - min_v for vn in v]
# checkの空きを見つける
p = slot_start # 検索開始位置
while True:
found = True
for offset in offsets:
if p + offset in check:
found = False
break
if found:
break
p += 1
base_s = p - min_v
return base_s
def update_slot_start(check, slot_start):
'''
darrayの空きスロット左端の更新
'''
p = slot_start
while True:
if p in check:
p += 1
else:
break
return p
def make_darray(base, check, db, db_keys, wdict):
'''
darrayを作成
'''
nd_inds = dict() # 遷移元データベース（部分文字列tuple => 末尾ノード位置）
slot_start = 1
for i, k in enumerate(db_keys):
if i % 1000000 == 0:
print(i, end=' ')
print('(' + str(slot_start) + ') ', end='')
v = db[k]
slot_start = update_slot_start(check, slot_start)
if len(k) == 0: # ルート
s = 1
for c in v:
t = base[s] + c
check[t] = s
nd_inds[() + (c,)] = t # 遷移先を登録
else: # ルート以外
s = nd_inds[k] # ノードsに移動
#pv(s)
if v == {0}: # 分岐しない葉ノードは圧縮
base[s] = -wdict[k]
else:
# checkの空きスロットからbase[s]の値を求める
base[s] = get_base_s(s, v, check, slot_start)
for c in v:
t = base[s] + c
check[t] = s
if c == 0: # 分岐のある葉ノード
base[t] = -wdict[k]
else:
nd_inds[k + (c,)] = t # 遷移先を登録
del(nd_inds[k]) # 使い終わったら消す（増えるので）
print()
def save_darray(base, check, cs):
'''
darrayをファイルに保存
'''
with open('darray.base', 'wb') as f:
ind_max = max(base.keys())
for i in range(0, ind_max + 1):
num = base[i] if i in base else 0
f.write(num.to_bytes(3, byteorder='little', signed=True))
with open('darray.check', 'wb') as f:
ind_max = max(check.keys())
for i in range(0, ind_max + 1):
num = check[i] if i in check else 0
f.write(num.to_bytes(3, byteorder='little'))
with open('darray.code', 'w', encoding='utf-8') as f:
print(*cs, sep='', file=f)
def main():
t1 = time.time()
# 見出し語リスト
words = []
if True:
with open('words.txt', 'r', encoding='utf-8') as f:
for ln in f:
words.append(ln.strip())
else:
words = ['でん', 'どこ', 'どん', 'どんちゃん' ,'どんどん', 'どんべぇ']
words = [''] + words # 先頭に空文字列を追加（必須）
print('len(words):', len(words))
# 分岐データベースを作成
# ついでに、文字テーブルとその逆引きも、この関数内で作っておく
db, db_keys, cs, c2code = get_branch_db(words)
print('len(cs):', len(cs))
print('len(db):', len(db))
# 単語辞書を作成（見出し語 => 単語ID）
# ただし見出し語は文字コードのtupleに変換
wdict = {tuple(c2code[c] for c in words[i]):i for i in range(len(words))}
# base配列とcheck配列をdictで表現
# ルートを登録
base = {1:1}
check = {1:0}
make_darray(base, check, db, db_keys, wdict)
print('len(base), len(check):', len(base), len(check))
print('max(base), max(check):', max(base), max(check))
# ファイル書き出し
save_darray(base, check, cs)
t2 = time.time()
print(int((t2 - t1) * 100 + 0.5) / 100, 's')
if __name__ == '__main__':
main()
# コード例４：double arrayの利用クラス DArray
class DArray:
def __init__(self):
with open('darray.base', 'rb') as f:
self._base = f.read()
with open('darray.check', 'rb') as f:
self._check = f.read()
with open('darray.code', 'r', encoding='utf-8') as f:
self._code = f.read()
self.c2code = {'':0}
for c in self._code:
self.c2code[c] = len(self.c2code)
def base(self, p):
base_p = int.from_bytes(self._base[3*p:3*(p+1)], byteorder='little', signed=True)
return base_p
def check(self, p):
check_p = int.from_bytes(self._check[3*p:3*(p+1)], byteorder='little')
return check_p
def search_gen(self, key):
s = 1
for i, c in enumerate(key):
if not c in self.c2code:
return
code = self.c2code[c]
t = self.base(s) + code
if self.check(t) == s:
if self.base(t) < 0:
yield i, -self.base(t)
else:
t2 = self.base(t)
if self.base(t2) < 0 and self.check(t2) == t:
yield i, -self.base(t2)
s = t
next
else:
return
# コード例５：DArrayを使ってテキスト検索する
import time
def readline_gen(fn):
'''
(1)ファイルの行を読む
'''
with open(fn, 'r', encoding='utf-8') as f:
for lnum, ln in enumerate(f):
yield ln.rstrip(), lnum
def get_str2scan_gen(rl_gen):
'''
(2)その行の文字列から各文字列位置を先頭とする部分文字列を作る
'''
for ln, lnum in rl_gen:
for start in range(len(ln)):
yield ln[start:], start, lnum
def search_incr_gen(gs_gen, da):
'''
(3)それぞれの部分文字列についてインクリメンタル検索をする
'''
for s, start, lnum in gs_gen:
for end, wid in da.search_gen(s):
yield (s[:end+1], wid, start, start + end, lnum)
def main():
# 長いページはここから => https://ja.wikipedia.org/wiki/特別:長いページ
fn = 'church_state.txt'
t1 = time.time()
da = DArray()
# 多段generator
gen1 = readline_gen(fn)
gen2 = get_str2scan_gen(gen1)
gen3 = search_incr_gen(gen2, da)
print('#', 'word', 'word_id', 'start', 'end', 'line_num', sep='\t')
ws = set()
for i, (word, wid, start, end, lnum) in enumerate(gen3):
ws.add(word)
if i < 10: # 先頭のいくつかだけ表示してみる
print(i, word, wid, start, end, lnum, sep='\t')
print()
print(i + 1, 'hits &', len(ws), 'unique words' )
t2 = time.time()
print(int((t2 - t1) * 100 + 0.5) / 100, 's')
if __name__ == '__main__':
main()