Jikken-search-engineをPythonで実装するメモ

python

参照

http://d.hatena.ne.jp/kzhk/20091202/p2

Java言語を用いて比較的に大きなプログラムの作成を行う．suffix arrayと呼ばれるデータ構造を用いた全文検索用インデックスを作り，それを用いて，Webファイルに対する全文検索エンジンを作成する．

http://www.osss.cs.tsukuba.ac.jp/kato/wiki/kato/index.php?Jikken-search-engine

Suffix Array

1-1 「与えられた文字列のsuffix arrayを作成するプログラムを作成せよ．」
def suffixArray(t):
    l = len(t)
    s = [(t[x:l] , x + 1) for x in range(l)]
    s.sort()
    suffix_array = [a[1] for a  in s]

    return suffix_array
1-2　「与えられた文字列に対し，その部分文字列を入力し，部分文字列が 出現する全位置を列挙する検索プログラムを作成せよ．（ヒント： suffix array上の2分探索を行う）」
# vim:fileencoding=utf-8

import math
import re

sa = [] #Suffix Array

#SuffixArray生成
def suffixArray(t):
    global sa

    l = len(t)
    sa = [(t[x:l] , x + 1) for x in range(l)]
    sa.sort()

    return False

#SuffixArrayを部分文字と先端でマッチするまで二分探査
def binarySearch(req):
    global sa

    maxi = len(sa) - 1
    mini = 0

    while mini + 1 != maxi:
        pnt = int(math.ceil(float(mini + maxi) / 2))

        data = sa[pnt][0]
        p = re.compile(req)
        match = p.match(data)

        if match != None:
            rangeSearch(mini, maxi, pnt, p)
            break
        elif req < data:
            maxi = pnt
        else:
            mini = pnt

    return False

#二分探索でマッチしたポイントから更に二方向に二分探索し、部分文字のある範囲を調べる
def rangeSearch(mini, maxi, pnt, p):
    global sa

    mini_con = pnt

    while mini_con + 1 != maxi:
        pnt_con = int(math.ceil(float(mini_con + maxi) / 2))

        data = sa[pnt_con][0]
        match = p.match(data)

        if match != None:
            mini_con = pnt_con
        else:
            maxi = pnt_con

    maxi_lim = mini_con

    maxi = pnt - 1

    while mini + 1 != maxi:
        pnt = int(math.ceil(float(mini + maxi) / 2))

        data = sa[pnt][0]
        match = p.match(data)

        if match != None:
            maxi = pnt
        else:
            mini = pnt

    mini_lim = maxi

    cnt  = [sa[a][1] for a in xrange(mini_lim, maxi_lim + 1)]
    cnt.sort()

    print cnt

def main():
    uri = 'abcdefghiabcjklmnabc'
    req = 'abc' #部分文字

    suffixArray(t)
    binarySearch(req)

if __name__ == '__main__':
    main()
1-3　「指定された1個のHTMLテキストファイルをメモリ中に読み込んで1個の文字列とし，それに対する suffix arrayをメモリ中に作成し，ユーザから入力された文字列を検索して，入力文字列が出現する全位置を列挙するプログラムを作成せよ．」
# vim:fileencoding=utf-8

import math
import re
import urllib2

'''
(1-2)
'''

def httpget(uri):
    opener = urllib2.build_opener()
    doc = opener.open(uri).read()
    return doc

def main():
    uri = 'http://www.osss.is.tsukuba.ac.jp/jikken-3nen/codeconv/CodeConvTOC.doc
.html'
    req = 'for' #部分文字

    t = httpget(uri)
    suffixArray(t)
    binarySearch(req)

if __name__ == '__main__':
    main()

つづく