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

Question

给定一个大文本文件(大约 500MB 的文本)，我必须找出该文件中字典单词的数量。用于检查它是否是单词的词典是用于优化查找的 trie。

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

[删除的代码]

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

r

拉

赛车

种族

赛车

赛科

赛马会

赛马场

赛马场

马场

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

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);
                }

            }

        }