4

これは、この応答と、ユーザーが投稿した疑似コード アルゴリズムに対するフォローアップの質問です。その質問については、年齢のためにコメントしませんでした。文字列を単語に分割できるかどうかを検証することにのみ関心があります。アルゴリズムは実際に文字列を分割する必要はありません。これは、リンクされた質問からの応答です。

S[1..length(w)] をブール エントリを持つテーブルとします。単語 w[1..i] を分割できる場合、S[i] は true です。次に、S[1] = isWord(w[1]) を設定し、i=2 を length(w) に計算します。

S[i] = (isWord[w[1..i] または {2..i} 内の任意の j: S[j-1] および isWord[j..i])。

このアルゴリズムを単純な python コードに翻訳していますが、正しく理解しているかどうかはわかりません。コード：

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, str_len):
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

関連する質問が 2 つあります。1) このコードは、リンクされたアルゴリズムを Python に適切に変換したものですか? もしそうなら、2) S を取得したので、文字列が単語だけで構成されているかどうかを判断するためにどのように使用すればよいですか? この場合、is_wordは単にリスト内の特定の単語を検索する関数です。まだトライとして実装していません。

更新: 提案された変更を含めるようにコードを更新した後、機能しません。これは更新されたコードです:

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, i): #THIS LINE WAS UPDATED
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

a_string = "carrotforever"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints FALSE

a_string = "hello"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints TRUE

Trueこれらの両方に対して返されるはずです。

4

3 に答える 3

2

これは、良い結果を返すコードの修正バージョンです。あなたの間違いは、疑似コード配列のインデックス付け（1から始まる）からpython配列のインデックス付け（0から始まる）への変換にあることに注意してください。したがって、 S[0] と S[1] には S[L-1]実際には計算されませんでした。この間違いは、S 値全体を出力することで簡単に追跡できます。最初の例では、「car」という単語の S[2] である必要がある S[3] が true に設定されていることがわかります。また、各位置をテストする代わりに、これまでに見つかった複合語のインデックスを保存することで、プロセスを高速化できます。

def is_all_words(a_string, dictionary):
    str_len = len(a_string)
    S = [False] * (str_len)
# I replaced is_word function by a simple list lookup, 
# feel free to replace it with whatever function you use. 
# tries or suffix tree are best for this.
    S[0] = (a_string[0] in dictionary) 
    for i in range(1, str_len):
        check = a_string[0:i+1] in dictionary # i+1 instead of i
        if (check):
            S[i] = check
    else:
        for j in range(0,i+1): # i+1 instead of i
            if (S[j-1] and (a_string[j:i+1] in dictionary)): # i+1 instead of i
            S[i] = True
            break


    return S

a_string = "carrotforever"
S = is_all_words(a_string, ["a","car","carrot","for","eve","forever"])
print(S[len(a_string)-1]) #prints TRUE

a_string = "helloworld"
S = is_all_words(a_string, ["hello","world"])
print(S[len(a_string)-1]) #prints TRUE
于 2012-04-23T03:23:36.760 に答える
1

1) 一見、良さそうに見える。ひとこと:for j in range(1, str_len):あるべきだfor j in range(1, i):と思う

2) S[str_len-1]==true の場合、文字列全体は完全な単語のみで構成される必要があります。

結局 S[i] が true の場合

  • 0 から i までの文字列全体が単一の辞書単語で構成されている
  • または S[j-1]==true with が存在しj<i、string[j:i] が単一の辞書単語である

したがって、S[str_len-1] が true の場合、文字列全体が辞書の単語から構成されます

于 2012-04-22T22:33:23.300 に答える