如何在没有分隔符的大文本文件中查找所有字典单词

Question

给定一个大的文本文件(大约500MB的文本(，我必须找到这个文件中的字典单词数。用于检查它是否是一个单词的字典是优化查找的尝试。

对于像"赛马场"这样的小输入，它应该返回 6 个单词，因为 {"race"、"course"、"racecourse"、"racecourse"、"a"、"our"、"ace"} 都是字典中的单词。我目前的方法效率不高：

[删除的代码]

这将遍历字符串并检查每个部分，例如：

r

RA

拉克

比赛

赛克

赛马科

消旋库

消旋

赛马

马场

在下一次迭代中，它将删除"r"并再次重复字符串"acecourse"。我还有另一个尝试可以防止计算重复的字符串。对于大文本文件来说，这是相当低效和错误的。有什么建议吗？

Answer 1

是的，你可以更快地做到这一点。假设字典已排序，则可以将二进制搜索与开始索引和结束索引一起使用。索引可确保在字典中搜索到最少的匹配项。我创建了索引器对象来跟踪和缩小每个搜索结果的范围。当没有要搜索的内容时，它会删除索引器。

代码为 C#：

        public class Indexer
        {
            public int DictStartIndex { get; set; }
            public int DictEndIndex { get; set; }
            public int CharCount { get; set; }
            public int CharPos { get; set; }
        }
        public class WordDictionaryComparer : IComparer<string>
        {
            public int Compare(string x, string y)
            {
                return x.CompareTo(y);
            }
        }

        public static void Main(string[] args)
        {
            List<string> dictionary = new List<string>() { "race", "course", "racecourse", "a", "our", "ace", "butter", "rectangle", "round" };
            dictionary.Sort();
            List<Indexer> indexers = new List<Indexer>();
            WordDictionaryComparer wdc = new WordDictionaryComparer();
            List<string> wordsFound = new List<string>();
            string line = "racecourse";
            for (int i = 0; i < line.Length; i++)
            {
                Indexer newIndexer = new Indexer();
                newIndexer.CharPos = i;
                newIndexer.DictEndIndex = dictionary.Count;
                indexers.Add(newIndexer);
                for (int j = indexers.Count - 1; j >= 0; j--)
                {
                    var oneIndexer = indexers[j];
                    oneIndexer.CharCount++;
                    string lookFor = line.Substring(oneIndexer.CharPos, oneIndexer.CharCount);
                    int index = dictionary.BinarySearch(oneIndexer.DictStartIndex, oneIndexer.DictEndIndex - oneIndexer.DictStartIndex, lookFor, wdc);
                    if (index > -1) wordsFound.Add(lookFor);
                    else index = ~index;
                    oneIndexer.DictStartIndex = index;
                    //GetEndIndex
                    string lookEnd = lookFor.Substring(0, lookFor.Length - 1) + (char)(line[i] + 1);
                    int endIndex = dictionary.BinarySearch(oneIndexer.DictStartIndex, oneIndexer.DictEndIndex - oneIndexer.DictStartIndex, lookEnd, wdc);
                    if (endIndex < 0) endIndex = ~endIndex;
                    oneIndexer.DictEndIndex = endIndex;
                    if (oneIndexer.DictEndIndex == oneIndexer.DictStartIndex) indexers.RemoveAt(j);
                }
            }
        }