0

OCR からの単語があり、近似一致のリストが必要です。maxFrom がなくても生きていける。サンプル コードは強引ですが、要件が定義されていることを願っています。600,000 のリストに対して、これには 2 秒かかります。FTSword.Word は文字列です。

理想的には、「findd」は 2 番目の d にのみ追加クレジットを付与します。そして、i が見つかると、f はクレジットを取得しません。力ずくでできます。私はその2秒を短縮しようとしています。提案されたソリューションをテストして報告します。

質問？？は。速くする方法は？（そしてより賢い）

ありがとう

            char[] find = new char[] { 'f', 'i', 'n', 'd' };
            char[] word;
            int maxFrom = 10;
            int minMatch = 3;
            int count;
            List<FTSword> matchWords = new List<FTSword>();
            foreach (FTSword ftsw in fTSwords)
            {
                if (ftsw.Word.Length < maxFrom)
                {
                    word = ftsw.Word.ToCharArray();
                    count = 0;
                    foreach (char fc in find)
                    {
                        foreach (char wc in word)
                        {
                            if (char.ToLower(wc) == char.ToLower(fc))
                            {
                                count++;
                                break;
                            }
                        }
                    }
                    if (count >= minMatch)
                    {
                        // Debug.WriteLine(count.ToString() + ftsw.Word);
                        matchWords.Add(ftsw);
                    }
                }
            }
            Debug.WriteLine(matchWords.Count.ToString());
4

2 に答える 2

1

char.ToLower()開始する前に小文字であることを確認した場合は、onfcを削除できます。

IndexOf()BCLの実装は、独自のループで管理できるよりも内部的に高速である可能性があるため、を使用して最初の（そしてその後の文字の出現）を見つけることもできます。

ループを逆に実行してみることもできます。これにより、スピードアップが可能になります。

 for (int i = arr.Length - 1; i >= 0; i--)

しかし、実際には、OCRの場合、ダメラウ・レーベンシュタインのような真の編集距離を実行する代わりに、文字列内の任意の位置から一致する文字を合計するのはなぜですか？

于 2012-04-18T04:09:53.127 に答える
1

一致する文字を探す 2 つのネストされたループがあるため、コア アルゴリズムは現在 O(n^2) です。find文字列内の各文字の文字数を含む Dictionary を使用して、その部分を簡単に O(n) にすることができます。

string find = "find";
var findMap = new Dictionary<char, int>();
foreach (char c in find)
{
    if (findMap.ContainsKey(c))
    {
        findMap[c] = findMap[c] + 1;
    }
    else
        findMap.Add(c, 1);
}
//findMap is pre-generated once

string word = "pint";
int count = 0;

//runs for each word in list, now in O(n)
foreach(char c in word)
{
    int charCount;
    if(findMap.TryGetValue(c, out charCount))
    {
        if(charCount > 0)
        {
            charCount--;
            findMap[c] = charCount;
            count++;
        }
    }
}
于 2012-04-18T03:44:55.263 に答える