Keywords Finder (Incinerator) - 検索ワードのハイライト表示

全問クリアしたはずの Incinerator に、新しい問題が追加されていた。

どんな問題？

Keywords Finder
http://www.checkio.org/mission/words-finder/

テキストに含まれるキーワードをすべて検索して、キーワード部分に＜span＞タグを追加せよ。

• キーワードはスペース区切りで複数指定される。
• 検索時には英字の大文字小文字は区別しない。
• キーワードの領域が重なった場合に、＜span＞タグがネストしてはならない。

キーワードの領域が重なったときがやっかいで、例えば、テキストが"Hello World!"のとき、
キーワードが "world or" であれば、

×: Hello <span>W<span>or</span>ld</span>!
○: Hello <span>World</span>!

キーワードが "Hell lo" であれば、

×: <span>Hel<span>lo</span></span> World!
○: <span>Hello</span> World!

と、＜span＞タグがネストしてはいけない。

どうやって解く？

キーワードの領域が重なったときの処理がポイントだろう。
キーワードが見つかる度に＜span＞タグを挿入するのではなく、先にすべての文字について、キーワード内かどうかを調べておいて、まとめて＜span＞タグを挿入していけばいいだろう。

すべて検索

キーワードを検索するときに、str.find()メソッドを使うと最初の1件しかヒットしないので、テキスト中の部分文字列をすべて検索する関数を作った。

def find_all(s, sub):
    i = 0
    while True:
        start = s.find(sub, i)
        if start == -1:
            break
        end = start + len(sub)
        yield start, end
        i = end

テキスト(s)の最初から最後まで調べて、部分文字列(sub)が見つかったら、その都度 yield する。

メイン部分では、まず、テキストの文字数分のフラグ（boolのリスト）を作成する。
フラグができたら、非キーワードとキーワードの区切り位置に＜span＞タグを挿入していく。

def checkio(text, words):
    # 文字数分のフラグを作成
    flags = [False] * len(text)
    for word in words.split():
        for start, end in find_all(text.lower(), word.lower()):
            for i in range(start, end):
                flags[i] = True

    # <span>タグを挿入
    result = ''
    prev_flag = False
    for flag, c in zip(flags, text):
        if not prev_flag and flag:  # フラグがFalseからTrueに変わったら、<span>を挿入
            result += '<span>'
        elif prev_flag and not flag:  # フラグがTrueからFalseに変わったら、</span>を挿入
            result += '</span>'
        result += c
        prev_flag = flag
    if prev_flag:
        result += '</span>'  # 文末がキーワードなら、最後に</span>を挿入

これでOK、さて、Run & Check

しかし、テストの途中でFAILになってしまった。

Your result: "<span>onetwothree</span>"
Right result: "<span>one</span><span>two</span><span>three</span>"
Fail: checkio("onetwothree", "three two one")

え？なんで "＜span＞onetwothree＜/span＞" がダメなの？

どうやら、＜span＞～＜/span＞が重なったときは一つにまとめるが、隣り合ったときは、まとめてはいけないようだ。なんか納得いかない仕様だなぁ。それと、問題文にちゃんと書いておいてくれ。

こういうケースをセルフチェックに付け加えておく。

    assert (checkio("Hello", "hell lo") == "<span>Hello</span>")
    assert (checkio("Hello", "hel lo") == "<span>Hel</span><span>lo</span>")
    assert (checkio("onetwothree", "three two one") == "<span>one</span><span>two</span><span>three</span>")

こうなると、フラグを使ったやり方では対応できないな。

最初から考え直す。

いったん、すべてのキーワードに＜span＞を挿入しておいて、HTMLチェッカーのように、ネストしているものを除外する、ってのはどうだろう。いや、余計に難しいか。
では、キーワード範囲を(start,end)のリストとして持っておいて、そこからspan範囲を作成していく、という形か？まず、startでソートして、範囲が重複するものがあれば、拡張していけばよさそうだ。

文字列の挿入

ところで、Pythonでは、strに挿入メソッドは無いんだな。
文字列の指定位置に部分文字列を挿入して、新たな文字列として返す関数を作成した。

def insert(s, sub, index):
    return s[:index] + sub + s[index:]

メイン部分はこうなった。

def checkio(text, words):
    # すべてのキーワードの範囲(start,end)をリストして、ソートしておく
    word_positions = sorted(p for word in words.split() for p in find_all(text.lower(), word.lower()))
    if not word_positions:
        return text

    # 重複範囲をチェックしていく
    span_positions = []
    span_start, span_end = word_positions[0]
    for start, end in word_positions[1:]:
        if span_end <= start:
            span_positions.append((span_start, span_end))
            span_start, span_end = start, end
        else:
            span_end = max(span_end, end)
    span_positions.append((span_start, span_end))

    # <span>タグを挿入
    for start, end in reversed(span_positions):
        text = insert(text, '</span>', end)
        text = insert(text, '<span>', start)

    return text

これでどーだ。

…またもエラー

Your result: "<span>aa</span><span>aa</span>"
Right result: "<span>aaaa</span>"
Fail: checkio("aaaa", "aa a")

え－、なんで？この場合 "＜span＞aaaa＜/span＞" になるのって、おかしくないか？

掲示板でも、あれこれ議論を呼んでいたが、なんせそういう仕様らしい。クライアント様には逆らえまへんわ。

ようするに、テキストが"aaaa"で、キーワードが"aa a"のときは、find_allで(0,2)(1,3)(2,4)を返すようにしなければいけないということだ。(0,2)(2,4)やら(0,1)(1,2)(2,3)(3,4)ではダメと。
find_all()を修正して対応した。ついでに、文字列の小文字化(lower)も find_all() 内でするようにした。

また、せっかく作ったinsert()だが、＜span＞と＜/span＞を同時に付け加えるようにしたので、不要になってしまった。

全部まとめてこう

def find_all(s, sub, ignore_case=True):
    """ Yields all (StartIndex, EndIndex) of substring
    """
    if ignore_case:
        s, sub = s.lower(), sub.lower()
    i = 0
    while True:
        start = s.find(sub, i)
        if start == -1:
            break
        yield start, start + len(sub)
        #i = start + len(sub)  # "aaaa","aa" -> (0,2),(2,4)
        i = start + 1          # "aaaa","aa" -> (0,2),(1,3),(2,4)

def checkio(text, words):
    # find all words
    word_positions = sorted(p for word in words.split() for p in find_all(text, word))
    if not word_positions:
        return text

    # merge overlapped
    span_positions = []
    span_start, span_end = word_positions[0]
    for start, end in word_positions[1:]:
        if span_end <= start:
            span_positions.append((span_start, span_end))
            span_start, span_end = start, end
        else:
            span_end = max(span_end, end)
    span_positions.append((span_start, span_end))

    # insert <span> tag
    for start, end in reversed(span_positions):
        text = text[:start] + '<span>' + text[start:end] + '</span>' + text[end:]

    return text

これでどーだ。

…Clear!

やったー！
いやー疲れた。
でも、やっぱりIncineratorは手応えがあるね。

ところで、実際のブラウザでも、複数キーワードで同時に検索できればいいのにな。