21

文字列を単語に分割する正しい方法は何ですか？（文字列にはスペースや句読点は含まれていません）

例：「stringintowords」->「StringIntoWords」

ここで使用するアルゴリズムを教えてください。

！更新：この質問は好奇心のためだけだと思う​​人のために。このアルゴリズムは、ドメイン名（ "sportandfishing .com"-> "SportAndFishing .com"）をカメラ化するために使用でき、このアルゴリズムは現在、aboutusdotorgによってこの変換を動的に行うために使用されています。

4

13 に答える 13

23

辞書を使用して単語isWord(w)であるかどうかをチェックする関数があると仮定します。簡単にするために、今のところ、ある単語に対してそのような分割が可能wかどうかだけを知りたいと仮定しましょう。wこれは、動的計画法で簡単に行うことができます。

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

S [i] =（isWord [w [1..i]または{2..i}の任意のjの場合：S[j-1]およびisWord[j..i]）。

辞書クエリが一定時間の場合、これにはO（length（w）^ 2）時間がかかります。実際に分割を見つけるには、trueに設定されている各S[i]に勝った分割を保存するだけです。これは、そのようなすべての分割を保存することにより、すべてのソリューションを列挙するように適合させることもできます。

于 2010-08-12T15:16:23.383 に答える
15

ここで多くの人が言及しているように、これは標準的で簡単な動的計画問題です。最良の解決策はFalkHüffnerによって与えられます。ただし、追加情報：

（a）isWordをトライで実装することを検討する必要があります。これにより、適切に使用すると（つまり、単語を段階的にテストすることで）時間を大幅に節約できます。

（b）「セグメンテーション動的計画法」と入力すると、デュークスでのこの講義など、疑似コードアルゴリズムを使用した大学レベルの講義から、より詳細な回答のスコアが得られます。どの辞書にも含まれない単語がある場合に実行します）。

于 2010-08-12T23:48:18.653 に答える
5

これを正しく行うには、辞書ベースのアプローチを使用する必要があり、それはひどく非効率的です。また、アルゴリズムから複数の結果を受け取ることを期待する必要があります。

例: windowsteamblog( http://windowsteamblog.com/名声の）

  • windows team blog
  • window steam blog
于 2010-08-12T11:21:58.663 に答える
5

これに関する学術文献にはかなりの部分があるはずです。検索したいキーワードは単語のセグメンテーションです。たとえば、この論文は有望に見えます。

一般に、マルコフモデルとビタビアルゴリズムについて学びたいと思うでしょう。後者は動的計画法アルゴリズムであり、可能なすべてのセグメンテーションを徹底的にテストすることなく、文字列のもっともらしいセグメンテーションを見つけることができます。ここでの重要な洞察は、最初のm文字にn個の可能なセグメンテーションがあり、最も可能性の高いセグメンテーションのみを見つけたい場合は、これらすべてを後続の文字に対して評価する必要はなく、評価を続けるだけでよいということです。最も可能性の高いもの。

于 2010-08-12T11:35:12.230 に答える
3

与えられた文字列に対して可能な分割の数を考えてみてください。n文字列に文字が含まれている場合はn-1、分割する可能性のある場所があります。たとえば、文字列catの場合、の前に分割したり、の前にa分割したりできますt。これにより、4つの分割が可能になります。

この問題は、文字列を分割する必要がある場所を選択することと見なすことができます。また、分割の数を選択する必要があります。したがって、Sum(i = 0 to n - 1, n - 1 choose i)分割の可能性があります。xとyの両方が1である二項係数の定理により、これはpow（2、n-1）に等しくなります。

確かに、この計算の多くは一般的なサブ問題に基づいているため、動的計画法によってアルゴリズムが高速化される可能性があります。頭から離れて、aを計算するboolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a wordことはかなり役に立ちます。可能なセグメンテーションの数はまだ指数関数的にありますが、初期の分割で単語が形成されなかった場合は、すぐにセグメンテーションを削除できます。j sub kその場合、解は= 。の条件を持つ整数のシーケンス（i0、j0、i1、j1、...）になりますi sub (k + 1)。

あなたの目標が正しくキャメルケースのURLである場合、私は問題を回避し、もう少し直接的なものを探します。URLのホームページを取得し、ソースHTMLからスペースと大文字を削除して、文字列を検索します。一致するものがある場合は、元のHTMLでそのセクションを見つけて、それを返します。次のように、元の文字列で発生する空白の量を宣言するNumSpacesの配列が必要になります。

Needle:       isashort    
Haystack:     This is a short phrase    
Preprocessed: thisisashortphrase   
NumSpaces   : 000011233333444444

そしてあなたの答えはから来るでしょう：

location = prepocessed.Search(Needle)
locationInOriginal = location + NumSpaces[location]
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location]
Haystack.substring(locationInOriginal, originalLength)

もちろん、madduckets.comのホームページのどこかに「MadDuckets」がなかった場合、これは壊れます。悲しいかな、それは指数関数的な問題を回避するためにあなたが支払う代償です。

于 2010-08-12T15:44:25.483 に答える
1

これは実際には辞書なしで（ある程度）行うことができます。基本的に、これは教師なし単語セグメンテーションの問題です。ドメイン名の大規模なリストを収集し、教師なしセグメンテーション学習アルゴリズム（例：Morfessor）を適用し、学習したモデルを新しいドメイン名に適用する必要があります。どれだけうまくいくかはわかりませんが（でも面白いでしょう）。

于 2011-05-16T14:44:31.223 に答える
1

これは基本的にナップサック問題のバリエーションであるため、必要なのは単語の包括的なリストとWikiでカバーされている解決策のいずれかです。

かなりのサイズの辞書を使用すると、これはめちゃくちゃリソースを消費し、時間のかかる操作になり、この問題が解決されるかどうかさえ確信できません。

于 2010-08-12T11:14:07.760 に答える
1

可能な単語のリストを作成し、長い単語から短い単語に並べ替えます。

リストの各エントリが文字列の最初の部分と照合されているかどうかを確認します。等しい場合は、これを削除して、文にスペースを追加します。これを繰り返します。

于 2010-08-12T11:15:28.157 に答える
1

実際、辞書を使えば、この問題はO(n)時間内に解決できます。より正確には(k + 1) * n、最悪の場合、nは文字列内の文字数であり、kは辞書内の最長の単語の長さです。

その上、アルゴリズムはあなたががらくたをスキップすることを可能にします。

これが私が少し前に作成したCommonLispの実用的な実装です：https ：//gist.github.com/3381522

于 2013-01-02T19:52:30.277 に答える
0

最善の策は、0からの部分文字列を辞書と比較し、一致するものを見つけたら、その単語を抽出して、その時点から新しい辞書検索を開始することです...しかし、エラーが発生しやすくなります。複数形とアポストロフィ（シンク、シンク）、およびその他の品詞に問題があります。

編集

「シングルエモーション」は「シングルエモーション」または「シングリーモーション」になりますか？

于 2010-08-12T11:11:47.150 に答える
0

その文字列を単語に分割できる唯一の方法は、辞書を使用することです。これはおそらくかなりのリソースを消費しますが。

于 2010-08-12T11:13:26.897 に答える
0

私は問題を見ていて、私がそれをどのようにしたかを共有できるかもしれないと思いました。アルゴリズムを言葉で説明するのは少し難しいので、最適化されたソリューションを擬似コードで共有できるかもしれません。

string mainword = "stringintowords";
array substrings = get_all_substrings(mainword);

/** this way, one does not check the dictionary to check for word validity 
 *  on every substring; It would only be queried once and for all, 
 *  eliminating multiple travels to the data storage
 */
string query = "select word from dictionary where word in " + substrings;
array validwords = execute(query).getArray();

validwords = validwords.sort(length, desc);

array segments = [];
while(mainword != ""){
    for(x = 0; x < validwords.length; x++){
        if(mainword.startswith(validwords[x])) {
            segments.push(validwords[x]);
            mainword = mainword.remove(v);
            x = 0;
        }
    }

    /**
     * remove the first character if any of valid words do not match, then start again
     * you may need to add the first character to the result if you want to
     */
    mainword = mainword.substring(1);
}

string result = segments.join(" ");
于 2012-12-23T15:50:29.147 に答える
0

実行時間がO（n ^ 2）の単純なJavaソリューション。

public class Solution {
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie)
    private HashSet<String> dictionary;

    public String parse(String s) {
        return parse(s, new HashMap<String, String>());
    }

    public String parse(String s, HashMap<String, String> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        if (dictionary.contains(s)) {
            return s;
        }
        for (int left = 1; left < s.length(); left++) {
            String leftSub = s.substring(0, left);
            if (!dictionary.contains(leftSub)) {
                continue;
            }
            String rightSub = s.substring(left);
            String rightParsed = parse(rightSub, map);
            if (rightParsed != null) {
                String parsed = leftSub + " " + rightParsed;
                map.put(s, parsed);
                return parsed;
            }
        }
        map.put(s, null);
        return null;
    }
}
于 2015-03-02T12:16:50.470 に答える