0

有来自 OCR 的单词，并且需要一个紧密匹配的列表。没有maxFrom也可以。示例代码是蛮力的，但希望它定义了要求。针对 600,000 的列表，这需要 2 秒。FTSword.Word 是一个字符串。

理想情况下，“findd”只会给第二个 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

您当前的核心算法是 O(n^2)，因为您有两个嵌套循环来寻找匹配的字符。您可以使用包含字符串中每个字符的字符计数的 Dictionary 轻松地制作该部分 O(n) find：

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 回答
1

char.ToLower()如果在开始之前确保它是小写的，则可以删除on fc。

您也可以尝试使用IndexOf()来查找第一个（然后是随后出现的字符），因为 BCL 实现在内部可能比您使用自己的循环管理的速度更快。

您也可以尝试反向运行循环，这可以提供加速：

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

但实际上，对于 OCR，为什么要总结字符串中任意位置的匹配字符，而不是像Damerau-Levenshtein那样进行真正的编辑距离？

于 2012-04-18T04:09:53.127 回答