4

数十億語のコーパスで検索したい数百万語があります。これを行うための効率的な方法は何でしょうか。

私はトライを考えていますが、トライのオープンソース実装は利用できますか？

ありがとうございました

- 更新しました -

正確に何が必要かについて、もう少し詳しく説明します。

ニュースソースをクロールし、単語の頻度に基づいて人気のある単語を取得するシステムがあります。百万の言葉があるかもしれません。

データは次のようになります。

Word1 Frequency1 Word2 Frequency2（タブ区切り）

また、上記の形式のデータを含む別のソースから最も人気のある単語（10億）を入手しました。

これが私が出力として取得したいものです。

  • 両方の情報源に共通する言葉
  • 単語は私たちのソースにのみ存在し、参照ソースには存在しません。
  • 単語は参照ソースにのみ存在し、ソースには存在しません。

上記の情報に対してcomm（bashコマンド）を使用できるのは単語だけです。commを使用して、両方の列ではなく1つの列とのみ比較する方法がわかりません。

システムはスケーラブルである必要があり、これを毎日実行して結果を比較したいと思います。また、おおよその一致を取得したいと思います。

だから、私はマップリデュースの仕事を書くことを考えています。以下のようにマップを作成して関数を減らす予定ですが、質問はほとんどありません。

Map
For each word
output key = word and value = structure{ filename,frequency}
done

Reduce
For each key
Iterate through all the values and check if both file1 and file2 are contained.
If yes, then write it to appropriate file.
If only in file1, write it to file1only file
If only in file2, write it to file2only file.
Done.

2つの質問があります。マップリデュースでは、2つのファイルを含むディレクトリを入力として指定できます。単語を読んでいるファイル名を取得する方法がわかりません。この情報を取得する方法は？削減フェーズはpart-xxxxxという名前のデフォルトファイルにのみ自動的に書き込むため、さまざまな出力ファイルに書き込むにはどうすればよいですか。さまざまな出力ファイルに書き込む方法。

これを読んでくれてありがとう。

4

9 に答える 9

2

MapReduceを使用すると、すべてを1つのステップまたはジョブで実行しようとすべきではありません。この問題を複数のステップに分割する必要があるようです。HDFSに保存されているデータを生成していて、ソースを知る必要があるため、おそらく次のような形式にする必要があります。

{SOURCE}、{WORD}、{FREQUENCY}

分散ファイルシステムについて話しているので、入力をfile1およびfile2として参照することは技術的に正しくないことを忘れないでください。参照データとソースデータの両方がクラスター全体に分散され、それぞれの断片が各ノードに配置されます。

次に、擬似コードの例から始めて、単語をソースとその頻度に関連付けるジョブを作成する必要があります。マッパーは問題なく機能しますが、reduceは単語をソースにリンクする必要があります。Map <source、frequency>を含む独自のWritableオブジェクトを作成する必要があります。これは、後続のフィルタージョブが処理できる中間データとしてHDFSに出力されます。

次に、このステップからの出力を3つの異なるMapReduceジョブへの入力として使用できます。それぞれがソースのさまざまな組み合わせを探しているところ。マッパーは同じデータを通過するだけなので、これらのジョブは非常に単純ですが、レデューサーはソースのさまざまな組み合わせについて各値をチェックします。

したがって、このアプローチを採用する場合は、4つのMapReduceジョブが必要になります。それぞれを手動で実行する必要はありません。各ジョブを順番に実行する単一のジョブを持つことができます。または、最後の3つのジョブは同じ入力データを使用するため、最初のジョブが終了したら、これら3つのジョブを同時に開始できます。これはおそらく、クラスターが管理できるデータと中間データの量、および各ジョブに必要なマッパー/リデューサーの数によって異なります。

この提案がお役に立てば幸いです。

于 2010-01-25T23:54:52.137 に答える
1

これは、Aho-Corasick文字列検索アルゴリズムが設計された仕事のように見えます。自分でコーディングしたことはありませんが、少しグーグルするとコードが見つかるはずです。

Rabin-Karpも機能する可能性がありますが、すべてが同じ長さではない場合に、複数のパターンでどのように機能するかわかりません。注：ウィキペディアの記事にあるマルチパターンの擬似コードは間違っているようです。しかし、あなたに出発点を与えるべきです。

于 2010-01-24T22:49:10.170 に答える
1

迅速で汚い精神で：

fgrep --mmap -f query-file corpus-file
于 2010-01-25T01:03:56.280 に答える
0

テキスト検索エンジンで使用されるデータ構造は、転置インデックスと呼ばれます。そして、言われているように、非常に優れたオープンソース検索エンジンはLuceneです。

于 2010-01-25T14:46:35.143 に答える
0

これをJavaで行う場合は、HashMapを使用します。ウィキペディアは、トライがわずかに優れている場合があることを示唆していますが、多くの違いが見られるかどうかはわかりません。

于 2010-01-24T22:40:50.900 に答える
0

そのパフォーマンスについてはよくわかりませんが、Pythonのnltkは、この種のことを行うように設計されています。つまり、大きなテキストコーパスをトークン化し、それらを比較できるようにするためです。「Pythonによる自然言語処理」という本は、このツールキットを利用しており、多くの例があります。オンラインで無料で利用できます。

于 2010-01-26T00:03:07.623 に答える
0

a.outにコンパイルされたtokenizer.cは、コーパスをトークン化してから、systemcloseシェルスクリプトを使用して効率的なパフォーマンスを実現できます。

 ./a.out <
/live/memory/var/cache/man/whatis  | sort | awk {'print $1'} | uniq -c
| sort -rn > file.txt
于 2010-01-26T00:10:16.797 に答える
0

デスクトップPCはこれを行うことができます。小さいデータセットはメモリに収まり、必要なのはそれだけです。

Pythonの場合：

# Load the words from the small file into one big hash set
small_set = set(line.split()[0] for line in open("small.txt", "r"))

# Open 3 output files.
f1 = open("common.txt", "w")
f2 = open("large_only.txt", "w")
f3 = open("small_only.txt", "w")

# Find all words in the large set that aren't in the small set.
for line in open("large.txt", "r"):
    word = line.split()[0]
    if word in small_set:
        f1.write(line)  # word is in both sets
        small_set.remove(word)
    else:
        f2.write(line)  # word is in large but not small

# Everything left over in small_set wasn't in the large_set.
for word in small_set:
    f3.write(word + "\n")

クラスターはそれをより速く行うことができます。しかし、あなたは家でこれを試すことができます。

于 2010-01-28T22:40:44.067 に答える
0

を使用できるのでcomm、入力ファイルをソートしておく必要があると思います。

commこれは、最初の列のみを調べるようなプログラムですが、入力の行全体を含む出力を生成します。入力がソートされている場合にのみ機能します！

これは完全なプログラムです。これをテキストファイルに入れて、コマンドラインから実行するだけです。

#!/usr/bin/env python
#
# comm.py - Compare 2 sorted files line by line, based on the first column.
# Usage:   python compare.py FILE1 FILE2 OUTFILE1 OUTFILE2 OUTFILE12
# OUTFILE1 receives all entries that are only in FILE1, etc.

import sys

def compare(f1, f2, out1, out2, out12):
    def get(f):
        line = f.readline()
        if line == '':
            return None
        first, rest = line.rstrip('\n').split('\t', 1)
        return first, rest, line

    e1 = get(f1)
    e2 = get(f2)
    while e1 and e2:
        if e1[0] == e2[0]:   # common entry
            out12.write(e1[0] + "\t" + e1[1] + "\t" + e2[1] + "\n")
            e1 = get(f1)
            e2 = get(f2)
        elif e1[0] < e2[0]:  # e1 is not in f2
            out1.write(e1[2])
            e1 = get(f1)
        else:                # e2 is not in f1
            out2.write(e2[2])
            e2 = get(f2)
    if e1:
        buf = e1[2]
        while buf:
            out1.write(buf)
            buf = f1.read(8192)
    if e2:
        buf = e2[2]
        while buf:
            out2.write(buf)
            buf = f2.read(8192)

compare(open(sys.argv[1], "r"),
        open(sys.argv[2], "r"),
        open(sys.argv[3], "w"),
        open(sys.argv[4], "w"),
        open(sys.argv[5], "w"))
于 2010-01-29T17:03:09.323 に答える