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

Question

给定一个大文本文件（大约500MB的文本），我必须找到该文件中的字典单词数。用于检查它是否是单词的字典是优化查找的特里。

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

[删除代码]

这将通过字符串并检查每个部分，如：

[R

出

RAC

种族

racec

raceco

跑马场

racecour

跑马场

跑马场

在下一次迭代中，它将删除'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);
                }

            }

        }