6

まず最初に、私は Python を初めて使用するので、ひどいことをしている場合は、この投稿の前に申し訳ありません。私はこの問題を割り当てられました：

次の問題に対する動的プログラミングのソリューションを考案したいと考えています: すべてのスペースが削除された一連の単語である可能性のある文字列があり、もしあれば、スペースを挿入する方法を見つけたいと考えています。有効な英単語を区切ります。たとえば、theyoutheevent は、「the you the vent」、「the Youth event」、または「they out he vent」からのものである可能性があります。入力がイーグルハスランドの場合、そのような方法はありません。あなたの仕事は、次の 2 つの方法で動的計画法のソリューションを実装することです。

  • 反復ボトムアップ バージョン
  • 再帰的記憶版

元の一連の単語には他の句読点 (ピリオドなど)、大文字、固有名詞が含まれていないと仮定します。すべての単語は、提供される辞書ファイルで利用できます。

だから私は2つの主な問題を抱えています:

  1. これは O(N^2) で実行でき、実行する必要があることを知っていますが、私のものはそうではないと思います
  2. ルックアップ テーブルは、時間の複雑さを軽減できると思われるすべての単語を追加していません。

私が欲しいもの：

  1. あらゆる種類の入力 (より良い方法、コードの間違い、ルックアップ テーブルを機能させる方法、ブール値のテーブルを使用して一連の有効な単語を作成する方法)
  2. 再帰バージョンに取り組む方法についていくつかのアイデアがありますが、反復ソリューションを解決できるようになったら、そこから再帰バージョンを設計できると思います。

誰かがこれを与えてくれた時間や努力にいつも感謝しています。

これが私の試みです：

#dictionary function returns True if word is found in dictionary false otherwise
def dictW(s):
    diction = open("diction10k.txt",'r') 
    for x in diction:
        x = x.strip("\n \r")
        if s == x:
            return True
    return False

def iterativeSplit(s):
    n = len(s)
    i = j = k = 0
    A = [-1] * n
    word = [""] * n
    booly = False
    for i in range(0, n):
        for j in range(0, i+1):
            prefix = s[j:i+1]
            for k in range(0, n):

                if word[k] == prefix:
                    #booly = True
                    A[k] = 1
                    #print "Array below at index k %d and word = %s"%(k,word[k])
                    #print A
            # print prefix, A[i]
            if(((A[i] == -1) or (A[i] == 0))):
                if (dictW(prefix)):
                    A[i] = 1
                    word[i] = prefix
                    #print word[i], i
                else:
                    A[i] = 0
    for i in range(0, n):
        print A[i]
4

2 に答える 2

4

英単語のセグメンテーションを行う方法の別の実際の例については、Python の wordsegment モジュールのソースを参照してください。単語とフレーズの頻度表を使用しているため、もう少し洗練されていますが、メモ化のアプローチを示しています。

特に、segmentメモ化アプローチを示します。

def segment(text):
    "Return a list of words that is the best segmenation of `text`."

    memo = dict()

    def search(text, prev='<s>'):
        if text == '':
            return 0.0, []

        def candidates():
            for prefix, suffix in divide(text):
                prefix_score = log10(score(prefix, prev))

                pair = (suffix, prefix)
                if pair not in memo:
                    memo[pair] = search(suffix, prefix)
                suffix_score, suffix_words = memo[pair]

                yield (prefix_score + suffix_score, [prefix] + suffix_words)

        return max(candidates())

    result_score, result_words = search(clean(text))

    return result_words

辞書内の単語に対して「1」を返し、そうでない場合は「0」を返すように関数を置き換えた場合score、回答に対して正のスコアの候補をすべて列挙するだけです。

于 2015-09-02T23:10:24.840 に答える
0

これがC++での解決策です。概念を読んで理解し、実装します。

このビデオは、DP アプローチを理解するのに非常に役立ちます。

私が役立つと思うもう 1 つのアプローチは、Trieデータ構造です。上記の問題を解決するためのより良い方法です。

于 2015-04-15T19:22:35.320 に答える