4


1

トリッキーな文字列マッチング

大きな文字列で部分文字列の最初のインデックスを見つけたい。 CamelCaseを個別の単語として処理することを除いて、単語全体と一致させるだけで、大文字と小文字を区別しないようにします。

以下のコードはトリックを行いますが、遅いです。 スピードアップしたいです。 助言がありますか? 正規表現を試してみましたが、すべてのエッジケースを処理する正規表現を見つけることができませんでした。

def word_start_index(text, seek_word):
    start_index = 0
    curr_word = ""
    def case_change():
        return curr_word and ch.isupper() and curr_word[-1].islower()
    def is_match():
        return curr_word.lower() == seek_word.lower()
    for i, ch in enumerate(text):
        if case_change() or not ch.isalnum():
            if is_match():
                return start_index
            curr_word = ""
            start_index = None
        if ch.isalnum():
            if start_index is None:
                start_index = i
            curr_word += ch
    if is_match():
        return start_index

if __name__ == "__main__":
    #            01234567890123456789012345
    test_text = "a_foobar_FooBar baz golf_CART"
    test_words = ["a", "foo", "bar", "baz", "golf", "cart", "fred"]

    for word in test_words:
        match_start = word_start_index(test_text, word)
        print match_start, word

出力:

0 a
9 foo
12 bar
16 baz
20 golf
25 cart
None fred

3 回答


3


word_emitter(以下)はテキスト文字列を受け取り、見つかった小文字の「単語」を1つずつ(位置とともに)生成します。

すべての下線をスペースに置き換えます。 次に、テキストをリストに分割します。 例えば、

"a_foobar_FooBar baz golf_CART Foo"

になる

['a', 'foobar', 'FooBar', 'baz', 'golf', 'CART', 'Foo']

もちろん、キャメルケースの単語を別の単語として扱うことも必要です。 したがって、上記のリストの各ピースに対して、正規表現パターン '(。* [a-z])(?= [A-Z])'`を使用してキャメルケースの単語を分割します。 この正規表現は、 `re`モジュールのルックフォワード演算子(?= …​) `を使用します。 おそらく、それは全体にとって最も難しい部分です。

次に、「word_emitter」は、単語とその関連する位置を一度に1つずつ生成します。

テキストを「単語」に分割する関数を作成したら、残りは簡単です。

また、ループの順序を切り替えたため、test_textを1回だけループします。 test_textsがtest_wordsに比べて非常に長い場合、これにより速度が向上します。

import re
import string
import itertools

nonspace=re.compile('(\S+)')
table = string.maketrans(
    '_.,!?;:"(){}@#$%^&*-+='+"'",
    '                       ',
    )

def piece_emitter(text):
    # This generator splits text into 2-tuples of (positions,pieces).
    # Given "a_foobar_FooBar" it returns
    # ((0,'a'),
    #  (2,'foobar'),
    #  (9,'FooBar'),
    #  )
    pos=0
    it=itertools.groupby(text,lambda w: w.isspace())
    for k,g in it:
        w=''.join(g)
        w=w.translate(table)
        it2=itertools.groupby(w,lambda w: w.isspace())
        for isspace,g2 in it2:
            word=''.join(g2)
            if not isspace:
                yield pos,word
            pos+=len(word)

def camel_splitter(word):
    # Given a word like 'FooBar', this generator yields
    # 'Foo', then 'Bar'.
    it=itertools.groupby(word,lambda w: w.isupper())
    for k,g in it:
        w=''.join(g)
        if len(w)==1:
            try:
                k1,g1=next(it)
                w+=''.join(g1)
            except StopIteration:
                pass
        yield w

def word_emitter(piece):
    # Given 'getFooBar', this generator yields in turn the elements of the sequence
    # ((0,'get'),
    #  (0,'getFoo'),
    #  (0,'getFooBar'),
    #  (3,'Foo'),
    #  (3,'FooBar'),
    #  (6,'Bar'),
    #  )
    # In each 2-tuple, the number is the starting position of the string,
    # followed by the fragment of camelCase word generated by camel_splitter.
    words=list(camel_splitter(piece))
    num_words=len(words)
    for i in range(0,num_words+1):
        prefix=''.join(words[:i])
        for step in range(1,num_words-i+1):
            word=''.join(words[i:i+step])
            yield len(prefix),word

def camel_search(text,words):
    words=dict.fromkeys(words,False)
    for pos,piece in piece_emitter(text):
        if not all(words[test_word] for test_word in words):
            for subpos,word in word_emitter(piece):
                for test_word in words:
                    if not words[test_word] and word.lower() == test_word.lower():
                        yield pos+subpos,word
                        words[test_word]=True
                        break
        else:
            break
    for word in words:
        if not words[word]:
            yield None,word

if __name__ == "__main__":
    #            01234567890123456789012345
    test_text = "a_foobar_FooBar baz golf_CART"
    test_words = ["a", "foo", "bar", "baz", "golf", "cart", "fred"]
    for pos,word in camel_search(test_text,test_words):
        print pos,word.lower()

プログラムのチェックに使用した単体テストは次のとおりです。

import unittest
import sys
import camel
import itertools

class Test(unittest.TestCase):
    def check(self,result,answer):
        for r,a in itertools.izip_longest(result,answer):
            if r!=a:
                print('%s != %s'%(r,a))
            self.assertTrue(r==a)

    def test_piece_emitter(self):
        tests=(("a_foobar_FooBar baz? golf_CART Foo 'food' getFooBaz",
                ((0,'a'),
                 (2,'foobar'),
                 (9,'FooBar'),
                 (16,'baz'),
                 (21,'golf'),
                 (26,'CART'),
                 (31,'Foo'),
                 (36,'food'),
                 (42,'getFooBaz'),
                )
                ),
            )
        for text,answer in tests:
            result=list(camel.piece_emitter(text))
            print(result)
            self.check(result,answer)
    def test_camel_splitter(self):
        tests=(('getFooBar',('get','Foo','Bar')),
               ('getFOObar',('get','FOO','bar')),
               ('Foo',('Foo',)),
               ('getFoo',('get','Foo')),
               ('foobar',('foobar',)),
               ('fooBar',('foo','Bar')),
               ('FooBar',('Foo','Bar')),
               ('a',('a',)),
               ('fooB',('foo','B')),
               ('FooB',('Foo','B')),
               ('FOOb',('FOO','b')),
               )
        for word,answer in tests:
            result=camel.camel_splitter(word)
            self.check(result,answer)
    def test_word_emitter(self):
        tests=(("a",
                ((0,'a'),) ),
               ('getFooBar',
                ((0,'get'),
                 (0,'getFoo'),
                 (0,'getFooBar'),
                 (3,'Foo'),
                 (3,'FooBar'),
                 (6,'Bar'),
                 )
                )
            )
        for text,answer in tests:
            result=list(camel.word_emitter(text))
            print(result)
            self.check(result,answer)

    def test_camel_search(self):
        tests=(("a_foobar_FooBar baz? golf_CART Foo 'food' getFooBaz",
                ("a", "foo", "bar", "baz", "golf", "cart", "fred", "food",
                  'FooBaz'),
                ((0,'a'),
                 (9,'Foo'),
                 (12,'Bar'),
                 (16,'baz'),
                 (21,'golf'),
                 (26,'CART'),
                 (36,'food'),
                 (45,'FooBaz'),
                 (None,'fred')
                )
                ),
               ("\"Foo\"",('Foo',),((1,'Foo'),)),
               ("getFooBar",('FooBar',),((3,'FooBar'),)),
            )
        for text,search_words,answer in tests:
            result=list(camel.camel_search(text,search_words))
            print(result)
            self.check(result,answer)

if __name__ == '__main__':
    unittest.main(argv = unittest.sys.argv + ['--verbose'])


2


正規表現を使用してこれを行っていた場合、おそらく次のようにします。

def word_start_index2(text, seek_word):
    camel_case = seek_word[0].upper() + seek_word[1:].lower()
    seek_word_i = ''.join('[' + c.lower() + c.upper() + ']'
                           for c in seek_word)
    regex1 = r'(?:(?<=[^a-zA-Z])|^)' + seek_word_i + r'(?=$|[^a-zA-Z])'
    regex2 = r'(?:(?<=[a-z]|[^A-Z])|^)' + camel_case + r'(?=$|[A-Z]|[^a-z])'
    regex = '%s|%s' % (regex1,  regex2)
    import re
    m = re.search(regex, text)
    if not m:
        return None
    else:
        return m.start()

ただし、これをお使いのバージョンに対してパフォーマンステストしたことはありませんが、より良いか悪いかを確認して、お知らせください。

私の答えは、いくつかのエッジケースであなたから異なる出力を与えるかもしれませんが、あなたのコメントでは、これらのケースを気にしないと言いました。

また、表記法「(?i)」を使用して、大文字と小文字を区別しない正規表現の一部をマークしようとしましたが、何らかの理由でこれが正しく機能しません。 その理由は説明できません。

最終的な自己決定:関数は引数を検証する必要がありますが、明確にするためにこのコードは省略されています。 少なくとも以下のチェックを追加する必要があります。

  • テキストは文字列でなければなりません

  • seek_wordは '[a-zA-Z] +'に一致する文字列でなければなりません


1


検索を高速化するインデックス付き:-)

from collections import defaultdict

class IndexedText(object):
    """ a indexed text """
    def __init__(self, text):
        self.text = text
        self._index()


    def word_start_index(self, word):
        l = len(word)
        w = word.lower()
        return self.index[word]

    def _index(self):
        self.index = defaultdict( list )

        def index( word, pos):
            self.index[word.lower()].append( pos )

        start = 0
        it = enumerate(self.text)
        lpos, lchar = it.next()
        WS = (' ','_')

        for pos, char in it:
            if lchar in WS and char not in WS:
                index( self.text[start:lpos], start )
                start = pos
            elif lchar.islower() and char.isupper(): # camelcase
                index( self.text[start:pos], start )
                start = pos
            lpos, lchar = pos, char

        # last word is missing
        index( self.text[start:], start )

if __name__ == "__main__":
    #            01234567890123456789012345
    test_text = "a_foobar_FooBar baz golf_CART"
    test_words = ["a", "foo", "bar", "baz", "golf", "cart", "fred"]

    index = IndexedText( test_text )

    for word in test_words:
        match_start = index.word_start_index( word )
        print match_start, word