10

私は2つか3つの英語の単語の組み合わせである複合文字列をたくさん持っています。

    e.g. "Spicejet" is a combination of the words "spice" and "jet"

私はこれらの個々の英語の単語をそのような複合文字列から分離する必要があります。私の辞書は約100000語で構成されます。

そのような複合文字列から個々の英語の単語を分離することができる最も効率的な方法は何でしょうか。

4

10 に答える 10

8

これを実行する必要がある時間または頻度はわかりませんが（1回限りの操作ですか？毎日ですか？毎週ですか？）、加重辞書をすばやく検索する必要があることは明らかです。

また、競合解決メカニズム、おそらく複数の可能な意味を持つタプルの競合を手動で解決するためのサイドキューが必要になります。

Triesを調べます。1つを使用すると、プレフィックスを効率的に見つける（そして重み付けする）ことができます。これはまさにあなたが探しているものです。

優れた辞書ソースから自分で試行を構築し、完全な単語でノードに重みを付けて、参照用の高品質のメカニズムを提供する必要があります。

ここでブレインストーミングを行いますが、データセットが主にデュプレットまたはトリプレットで構成されていることがわかっている場合は、複数のTrieルックアップを回避できます。たとえば、「Spic」を検索してから「ejet」を検索し、両方の結果のスコアが低いことがわかります。 'Spice'と'Jet'に放棄します。両方の試行で、2つの間の良好な組み合わせ結果が得られます。

また、任意または動的な制限までの最も一般的なプレフィックスで頻度分析を利用することを検討します。たとえば、「'」または「un」または「in」をフィルタリングし、それに応じてそれらに重みを付けます。

楽しい問題のようですね、頑張ってください！

于 2009-08-18T04:22:00.403 に答える
4

あなたが答えたように「入力の可能な最大の分割」を見つけることが目的である場合、グラフ理論を使用すると、アルゴリズムはかなり簡単になります。複合語を取り、各文字の前後に頂点を持つグラフを作成します。文字列内の各インデックスの頂点と、末尾の 1 つの頂点があります。次に、複合語の部分文字列であるすべての有効な単語を辞書で検索します。次に、正当な部分文字列ごとに、部分文字列の最初の文字の前の頂点と部分文字列の最後の文字の後の頂点を結ぶグラフに、重み 1 のエッジを追加します。最後に、最短パス アルゴリズムを使用して、最初の頂点と最後の頂点の間のエッジが最も少ないパスを見つけます。

擬似コードは次のようなものです。

parseWords(compoundWord)
    # Make the graph
    graph = makeGraph()
    N = compoundWord.length
    for index = 0 to N
        graph.addVertex(i)

    # Add the edges for each word
    for index = 0 to N - 1
        for length = 1 to min(N - index, MAX_WORD_LENGTH)
            potentialWord = compoundWord.substr(index, length)
            if dictionary.isElement(potentialWord)
                graph.addEdge(index, index + length, 1)

    # Now find a list of edges which define the shortest path
    edges = graph.shortestPath(0, N)

    # Change these edges back into words.
    result = makeList()
    for e in edges
        result.add(compoundWord.substr(e.start, e.stop - e.start + 1))
    return result

明らかに、私はこの疑似コードをテストしていません。また、いくつかのオフバイワンのインデックス作成エラーがある可能性があり、バグチェックはありませんが、基本的な考え方はそこにあります。私は学校でこれと似たようなことをしましたが、かなりうまくいきました。エッジ作成ループは O(M * N) です。ここで、N は複合語の長さであり、M は辞書内の最大語長または N (いずれか小さい方) です。最短パス アルゴリズムの実行時間は、選択したアルゴリズムによって異なります。ダイクストラが最もすぐに思い浮かびます。可能な最大エッジはN ^ 2であるため、ランタイムはO(N ^ 2 * log(N))であると思います。

任意の最短パス アルゴリズムを使用できます。さまざまな長所と短所を持つ最短経路アルゴリズムがいくつかありますが、あなたの場合、違いはそれほど重要ではないと思います。複合語を分割するために可能な限り少ない単語を見つけようとする代わりに、可能な限り多くの単語を見つけたい場合は、エッジに負の重みを与え、負の重みを許可するアルゴリズムで最短経路を見つけようとします。

于 2009-08-18T08:23:29.370 に答える
2

そして、どのように物事を分割するかを決定しますか？Webを見回すと、他の意味を持つことが判明したURLの例が見つかります。

あなたが続けるための資本を持っていなかったと仮定して、あなたはこれらをどうしますか（現在頭に浮かぶもの、私はもっとあることを知っています）：

PenIsland
KidsExchange
TherapistFinder

最後の1つは、2つの単語が一緒に実行されることですが、複合語ではないため、特に問題があります。これを分割すると、意味が完全に変わります。

于 2009-08-18T04:18:26.633 に答える
2

それで、単語が与えられた場合、それは他の2つの英語の単語で構成される複合語ですか？このようなすべての複合語に対してある種のルックアップテーブルを作成することもできますが、候補を調べて英語の単語と照合しようとすると、誤検知が発生します。

編集：いくつかの例を提供するために行かなければならないように見えます。私が考えていた言葉は次のとおりです。

accustomednesses != accustomed + nesses
adulthoods != adult + hoods
agreeabilities != agree + abilities
willingest != will + ingest
windlasses != wind + lasses
withstanding != with + standing
yourselves != yours + elves
zoomorphic != zoom + orphic
ambassadorships != ambassador + ships
allotropes != allot + ropes

ここに、要点を説明するために試すためのPythonコードがいくつかあります。ディスク上の辞書を入手して、試してみてください。

from __future__ import with_statement

def opendict(dictionary=r"g:\words\words(3).txt"):
    with open(dictionary, "r") as f:
        return set(line.strip() for line in f)

if __name__ == '__main__':
    s = opendict()
    for word in sorted(s):
        if len(word) >= 10:
            for i in range(4, len(word)-4):
                left, right = word[:i], word[i:]
                if (left in s) and (right in s):
                    if right not in ('nesses', ):
                        print word, left, right
于 2009-08-18T04:20:56.177 に答える
2

TrieまたはDAWGデータ構造に辞書を保存したいようです。

Trie はすでに単語を複合語として格納しています。したがって、「spicejet」は「spice jet」として保存されます。* は単語の終わりを示します。必要なのは、複合語を辞書で調べて、ヒットした語末ターミネータの数を追跡することだけです。そこから、各部分文字列を試す必要があります (この例では、「jet」が単語かどうかまだわからないため、調べる必要があります)。

于 2009-08-18T04:08:04.660 に答える
1

同様の質問が最近尋ねられました: Word-separating algorithm . 分割数を制限したい場合は、各タプルの分割数を追跡します (つまり、ペアではなくトリプル)。

于 2009-08-18T07:07:09.353 に答える
1

合理的な複合語からの部分文字列の数は比較的少ない (最小長は 2) と思います。たとえば、「spicejet」の場合、次のようになります。

'sp', 'pi', 'ic', 'ce', 'ej', 'je', 'et',
'spi', 'pic', 'ice', 'cej', 'eje', 'jet',
'spic', 'pice', 'icej', 'ceje', 'ejet',
'spice', 'picej', 'iceje', 'cejet',
'spicej', 'piceje', 'icejet',
'spiceje' 'picejet'

... 26 の部分文字列。

したがって、それらすべてを生成する関数を見つけます (2、3、4 のストライドを使用して文字列を横切ってスライド(len(yourstring) - 1)し、セットまたはハッシュ テーブル内のそれぞれを単純にチェックします。

于 2009-08-18T04:37:42.727 に答える
1

単語の存在は、トライを使用するか、より単純にセット (つまり、ハッシュ テーブル) を使用して行うことができます。適切な関数が与えられた場合、次のことができます。

# python-ish pseudocode
def splitword(word):
    # word is a character array indexed from 0..n-1

    for i from 1 to n-1:
        head = word[:i]  # first i characters
        tail = word[i:]  # everything else

        if is_word(head):
            if i == n-1:
                return [head]   # this was the only valid word; return it as a 1-element list
            else:
                rest = splitword(tail)
                if rest != []:   # check whether we successfully split the tail into words
                    return [head] + rest

    return []  # No successful split found, and 'word' is not a word.

基本的に、さまざまなブレークポイントを試して、単語を作成できるかどうかを確認してください。再帰とは、成功した分割が見つかるまでバックトラックすることを意味します。

もちろん、これでは必要な分割が見つからない場合があります。これを変更して (単に最初に見つかったものではなく) すべての可能な分割を返すようにし、何らかの加重合計を実行して、一般的ではない単語よりも一般的な単語を優先することができます。

于 2009-08-18T04:38:10.963 に答える
1

これは非常に難しい問題になる可能性があり、単純な一般的な解決策はありません (小さなサブセットで機能するヒューリスティックがある場合があります)。

名前が形態素の連結によって構成される化学では、まさにこの問題に直面しています。例は次のとおりです。

ethylmethylketone

形態素は次のとおりです。

ethyl methyl and ketone

オートマトンと最大エントロピーを使用してこれに取り組みます。コードは Sourceforge で入手できます。

http://www.sf.net/projects/oscar3-chem

ただし、多少の作業が必要になることに注意してください。

私たちはあいまいさに遭遇することがありますが、それを報告する良い方法をまだ見つけていません。

ペンアイランドとペニスランドを区別するには、ドメイン固有のヒューリスティックが必要です。解釈の可能性は、使用されているコーパスによって異なります。言語の問題は、分析されているドメインまたはドメインから独立していません。

別の例として、文字列

weeknight

として解析できます

wee knight

また

week night

どちらも「adj-noun」または「noun-noun」の形式に従うという点で「正しい」です。どちらも「理にかなって」おり、どちらを選択するかは使用領域によって異なります。ファンタジー ゲームでは前者の可能性が高く、商取引では後者の可能性が高くなります。この種の問題がある場合は、専門家によって注釈が付けられた合意された使用法のコーパスがあると便利です (技術的には、自然言語処理の「ゴールド スタンダード」)。

于 2009-08-23T17:16:54.720 に答える
0

次のアルゴリズムを使用します。

  1. 分割する単語のソート済みリストと、拒否された単語のソート済みリスト（辞書）から始めます。

  2. 保存するオブジェクトの結果リストを作成します：残りの単語と一致した単語のリスト。

  3. 結果リストに残りの単語として分割する単語を入力します。

  4. マージアルゴリズムと同様の方法で、結果の配列と辞書を同時にウォークスルーします。常に2つのうち最小のものを増やします。このようにして、1回のパスで一致する可能性のあるすべてのペアを比較できます。

  5. 一致する単語、つまり辞書の単語で始まる分割単語を見つけたら、一致する辞書の単語と結果リストの残りの部分を置き換えます。可能な倍数を考慮に入れる必要があります。

  6. 残りの部分が空であるときはいつでも、あなたは最終的な結果を見つけました。

  7. 「左側」に一致するものが見つからない場合、つまり、一致しないために結果ポインターをインクリメントするたびに、対応する結果項目を削除します。この単語には一致するものがなく、分割できません。

  8. リストの一番下に到達すると、部分的な結果のリストが表示されます。これが空になるまでループを繰り返します-ポイント4に進みます。

于 2009-08-18T07:48:52.217 に答える