DouKaku?beta

challenge 文字列リストをTRIE Optimizeされた正規表現に

これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。

ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。

なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。

とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。

Dan the Regexp Assembler

see: Trie (en.wikipedia) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
while(<>){
    chomp;
    next unless $_;
    $ra->add($_);
}
print $ra->re, "\n"
__END__

% grep program /usr/share/dict/words 
program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer

% grep program /usr/share/dict/words | perl sample.pl 
(?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)
post comment

Posted feedbacks - Python

素朴な方法で

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys
import re

class Node(dict):
    def __init__(self, c, acceptable, children = None):
        if children is not None:
            super(Node, self).__init__(children)
        else:
            super(Node, self).__init__()

        self.c = c
        self.acceptable = acceptable

    def get_pattern(self):
        s = re.escape(self.c)
        trail = '|'.join(child.get_pattern() for child in self.itervalues())
        if trail:
            s += '(?:%s)' % trail
            if self.acceptable:
                s += '?'
        return s

    def optimize(self):
        children = dict()
        for child in self.itervalues():
            optimized = child.optimize()
            children[optimized.c] = optimized

        if len(children) == 1 and not self.acceptable:
            child = children.values()[0]
            c = self.c + child.c
            acceptable = child.acceptable
            return Node(c, acceptable, child)
        else:
            return Node(self.c, self.acceptable, children)

class Trie(object):
    def __init__(self, root = None):
        if root is None:
            self.root = Node('', False)
        else:
            self.root = root

    def add(self, word):
        node = self.root

        for c in word:
            if c not in node:
                node[c] = Node(c, False)
            node = node[c]
        node.acceptable = True

    def get_pattern(self):
        return self.root.get_pattern()

    def optimize(self):
        return Trie(self.root.optimize())

def main(args):
    import fileinput

    trie = Trie()
    for line in fileinput.input(args):
        word = line.strip()
        trie.add(word)

    trie = trie.optimize()
    print trie.get_pattern()

if __name__ == '__main__':
    main(sys.argv[1:])

あぁ、よく考えれば TRIE そのものをいじらなくてもいいな。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import sys
import re

class Node(dict):
    def __init__(self, c, acceptable, children = None):
        if children is not None:
            super(Node, self).__init__(children)
        else:
            super(Node, self).__init__()

        self.c = c
        self.acceptable = acceptable

    def get_pattern(self):
        s = re.escape(self.c)
        if len(self) > 0:
            if len(self) == 1 and not self.acceptable:
                s += self.values()[0].get_pattern()
            else:
                s += '(?:%s)' % '|'.join(c.get_pattern() for c in self.itervalues())

            if self.acceptable:
                s += '?'
        return s

class Trie(object):
    def __init__(self, root = None):
        if root is None:
            self.root = Node('', False)
        else:
            self.root = root

    def add(self, word):
        node = self.root

        for c in word:
            if c not in node:
                node[c] = Node(c, False)
            node = node[c]
        node.acceptable = True

    def get_pattern(self):
        return self.root.get_pattern()

def main(args):
    import fileinput

    trie = Trie()
    for line in fileinput.input(args):
        word = line.strip()
        trie.add(word)

    print trie.get_pattern()

if __name__ == '__main__':
    main(sys.argv[1:])

こういうやり方もあるよ、ということで。

  1. 文字列を辞書順にソート
  2. 隣り合う文字列同士の共通接頭辞長(lcps)を計算

で、後はある範囲で lcp の最小値が共通接頭辞の長さで、最小値の位置でリストを分割すれば分割統治法でパターンを構築できると。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys
import re

SLIM_RE = False

class RangeError(Exception):
    pass

def lcp(a, b):
    "returns length of longest common prefix"
    i = 0
    l = min(len(a), len(b))
    while i < l and a[i] == b[i]:
        i += 1
    return i

def min_index(l, first, last):
    "returns index of minimum value in [first:last]"
    if last - first <= 0:
        raise RangeError()
    i = first
    for j in xrange(first + 1, last):
        if l[j] < l[i]:
            i = j
    return i

def get_pattern(words, lcps, level, first, last):
    "get optimized regular expression from list of words which is sorted"
    if last - first == 1:
        return re.escape(words[first][level:])

    m = min_index(lcps, first, last - 1)
    prefix = words[first][level:lcps[m]]
    sub = (get_pattern(words, lcps, lcps[m], first, m + 1),
           get_pattern(words, lcps, lcps[m], m + 1, last))

    if SLIM_RE:
        pattern = '%s(?:%s)' % (re.escape(prefix), '|'.join(filter(bool, sub)))
        if len(words[m]) == lcps[m]:
            pattern += '?'
    else:
        pattern = '%s(?:%s|%s)' % (re.escape(prefix), sub[0], sub[1])
    return pattern

def main(args):
    import fileinput

    words = []
    for line in fileinput.input(args):
        words.append(line.strip())

    words.sort()
    lcps = [lcp(a, b) for a, b in zip(words[:-1], words[1:])]
    pattern = get_pattern(words, lcps, 0, 0, len(words))
    print pattern

    pat = re.compile(pattern)
    for word in words:
        if not pat.match(word):
            print >>sys.stderr, 'not match with %s' % word

if __name__ == '__main__':
    main(sys.argv[1:])


内部ではTRIEを使っていませんが、出力はお題でのサンプルと、
少なくともこの入力に関しては、同じになっています。

お題の解釈が出力だけを要求しているようにも読めるので、
とりあえず投稿します。

ちなみにカッコの中に'-xism'がある正規表現は
pythonのreモジュールでは使えないようです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
import re

def f1(l):
  if len(l) == 1:
    return l[0]

  r = '^(?:%s%s)' % ('(?:'.join(list(l[0])), ')?' * (len(l[0])-1))
  b = []
  c = []
  for s in l:
    s = s.rstrip()
    m = re.findall(r, s)
    if m:
      b.append((m[0], s))
    else:
      c.append(s)

  a = min([t[0] for t in b])
  flg = bool([t[1] for t in b if a == t[1]])
  b = [t[1][len(a):] for t in b if len(t[1]) != len(a)]
  if b:
    a = '%s(?:%s)%s' % (a, f1(b), '?' if flg else '')
  if c:
    c = f1(c)
    a = '%s|%s' % ((a, c) if len(a) > len(c) else (c, a))
  return a

def f(l):
  return '(?-xism:%s)' % f1(l)
#  return '(?:%s)' % f1(l)

if __name__ == '__main__':
  print f(sys.stdin.readlines())

しまった。言語の指定忘れてた。Pythonです。


Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]