Как найти все словарные слова в большом текстовом файле без разделителей?

Question

Учитывая большой текстовый файл (около 500 МБ текста), я должен найти количество слов словаря в этом файле.Словарь, используемый для проверки того, является ли это слово трийским для оптимизированного поиска.

Для небольшого ввода, такого как "ипподром", он должен возвращать 6 слов, потому что {"гонка", "курс", "гонка", "a", "our", "ace"} - все слова в словаре.Мой текущий метод не эффективен:

[Удаленный код]

Это проходит через строку и проверяет каждый раздел как:

r

ra

rac

race

racec

raceco

racecou

racecour

racecours

racecourse

В следующей итерации он удалит '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);
                }

            }

        }