3

大きな文字列で重複するフレーズを効率的に見つける方法を見つけようとしています。文字列には、空のスペースで区切られた数百または数千の単語が含まれます。現在使用している以下のコードを含めましたが、重複するフレーズを見つけるのは非常に非効率的です。

    public static string FindDuplicateSubstringFast(string s, string keyword, bool allowOverlap = true)
{
    int matchPos = 0, maxLength = 0;
    if (s.ToLower().Contains(keyword.ToLower()))
        for (int shift = 1; shift < s.Length; shift++)
        {
            int matchCount = 0;
            for (int i = 0; i < s.Length - shift; i++)
            {

                if (s[i] == s[i + shift])
                {
                    matchCount++;
                    if (matchCount > maxLength)
                    {
                        maxLength = matchCount;
                        matchPos = i - matchCount + 1;
                    }
                    if (!allowOverlap && (matchCount == shift))
                    {
                        // we have found the largest allowable match 
                        // for this shift.
                        break;
                    }
                }
                else matchCount = 0;
            }
        }
    string newbs = s.Substring(matchPos, maxLength);
    if (maxLength > 3) return s.Substring(matchPos, maxLength);
    else return null;
}

上記のコード例を見つけました @ Find duplicate content in string?

このメソッドはすべての文字を処理しており、各単語をループする方法を見つけたいと考えています。これを行う最善の方法が何であるかはわかりません。空のスペースで文字列を分割して、単語をリストに入れることができると考えていました。リストを反復することは、私が今行っているようにすべての文字を反復するよりもはるかに効率的です。ただし、リストを反復処理して重複するフレーズを見つける方法がわかりません。

リストを反復処理して重複するフレーズを見つけるアルゴリズムを誰かが見つけ出すのを手伝ってくれたら、とても感謝しています。また、大きな文字列内で重複するフレーズを見つけるための他のアイデアや方法も歓迎します。

さらに情報が必要な場合はお知らせください。

編集: これは大きな文字列の例です {この例では小さい}

Lorem Ipsum は、印刷および植字業界の単なるダミー テキストです。Lorem Ipsum は、1500 年代以来、業界標準のダミーテキストでした。

たとえば、日本酒「Lorem Ipsum」は重複フレーズになります。「Lorem Ipsum」と、文字列に複数回出現するその他の重複フレーズを返す必要があります。

4

1 に答える 1

6 
string[] split = BigString.Split(' ').ToLower();
var duplicates = new Dictionary<string, int>();
for (int i = 0;i<split.Length;i++)
{
    int j=i;
    string s = split[i] + " ";
    while(i+j<split.Length)
    {
        j++;
        s += split[j] + " ";
        if (Regex.Matches(BigString.ToLower(), s).Count ==1) break;
        duplicates[s] = Regex.Matches(BigString.ToLower(), s).Count;
    }
}

これで、辞書にはすべてのフレーズと「サブフレーズ」が含まれます。たとえば、「Lorem Ipsum Dolor」は「Lorem Ipsum」と「Lorem Ipsum Dolor」を検索します。それが興味のない場合は、のKeysCollection をループするだけですduplicates。あるキーが別のキーの部分文字列であり、それらの値が同じである場合は、そのキーを削除します。

于 2013-09-28T22:57:21.843 に答える