辞書に登録されている語をテキスト中から検索する

C++ Python

あー、Computer Science 的にそういうのは AC 法(Aho-Corasick algorithm) で Trie 使ってやるのが正道な気がする。で、一度作った TRIE は保存しておけばよい。
Python なら AC 法を実装した pytst という拡張ライブラリがあるので、これを使えば簡単。Ruby への移植版もある。

import sys
import tst

def main(args, options):
    trie = tst.TST()

    fp = file(options.list_file)
    try:
        for line in fp:
            trie[line.rstrip()] = None
    finally:
        fp.close()

    if len(args) == 0:
        result = trie.scan(sys.stdin.read(), tst.TupleListAction())
        if len(result) > 0:
            print "stdin match"
    else:
        for filename in args:
            fp = file(filename)
            result = trie.scan(fp.read(), tst.TupleListAction())
            fp.close()
            if len(result) > 0:
                print filename


if __name__ == '__main__':
    import optparse
    parser = optparse.OptionParser()
    parser.add_option('--list', dest='list_file', type='string')
    (options, args) = parser.parse_args()
    main(args, options)

ここでは実行時に TRIE を構築しているが、TST オブジェクトには TRIE の load/save を行う read_from_file, write_to_file というメソッドがあるので、実用的にはそれらを使って構築済みの TRIE をロードしたほうが良い。
C++ なら dartsという TRIE 実装のライブラリがある。

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <darts.h>

static int check_url(std::istream& in, Darts::DoubleArray& da)
{
    std::string content;
    std::string line;
    Darts::DoubleArray::result_pair_type result;

    while (!in.eof()) {
        getline(in, line);
        const char* str = line.c_str();
        size_t len = line.length();

        for (int i = 0; i < len; i++) {
            if (da.commonPrefixSearch(str + i, &result, 1, len - i) > 0) {
                return 1;
            }
        }
    }

    return 0;
}

static void usage(const char* progname)
{
    std::cerr << "Usage: " << progname << " double-array [filenames]" << std::endl;
    exit(1);
}

int main(int argc, char** argv)
{
    Darts::DoubleArray da;

    if (argc < 2) {
        usage(argv[0]);
    }

    const char* da_filename = argv[1];
    if (da.open(da_filename) != 0) {
        std::cerr << "failed to load double-array" << std::endl;
        exit(2);
    }

    if (argc == 2) {
        if (check_url(std::cin, da)) {
            std::cout << "<stdin>" << std::endl;
            return 0;
        } else {
            return 1;
        }
    } else {
        int retcode = 1;
        for (int i = 2; i < argc; i++) {
            const char* filename = argv[i];
            std::ifstream in(filename);
            if (!in) {
                std::cerr << "failed to open `" << filename << "'" << std::endl;
                return 2;
            }
            if (check_url(in, da)) {
                std::cout << filename << std::endl;
                retcode = 0;
            }
        }
        return retcode;
    }
}

こちらは TRIE を使うものの AC 法ではない。TRIE は darts 付属の mkdarts を使って作成しておく。

% sort urls.txt > urls.sorted
% mkdarts urls.sorted urls.da

自分は、darts のコードを Java に移植して使ってたりするけど、20万件程度ならさくさく動く。まぁ、固有表現辞書だから URL 見たいに長い文字列じゃないけど。