Алгоритм расстояния редактирования
iPhone 6 Plus позволяет использовать больше кнопок на панели вкладок в альбомном режиме, чем в портретном. К сожалению, это означает, что он сбрасывает массив customizableViewControllers всякий раз, когда устройство поворачивается, и ни один из ответов здесь не помог мне.
У меня уже был свой собственный подкласс UITabBarController, и переопределение методов установки и получения для customizableViewControllers было единственным надежным способом удаления кнопки «Редактировать» из экрана «Дополнительно»:
- (NSArray *)customizableViewControllers
{
return nil;
}
- (void)setCustomizableViewControllers:(NSArray*)controllers
{
//do nothing
}
2 ответа
Я попытаюсь сформулировать это по-другому.
Изначально существует n слов, заданных как набор слов из Словаря. Далее приведены слова 'm', которые являются словами запроса, и для каждого слова запроса мне нужно найти, существует ли слово уже в словаре (расстояние редактирования '0') или общее количество слов в словаре, которые находятся на расстоянии редактирования 1 или 2 из словаря слов.
Я надеюсь, что вопрос теперь ясен.
Что ж, время истекает, если временная сложность равна (m * n) * n. Наивное использование алгоритма DP Edit Distance истекает. Даже вычисление диагональных элементов 2 * k + 1 тайм-аут, где k - порог, здесь k = 3. в приведенном выше случае.
PS: BK Tree должно быть достаточно для этой цели. Любые ссылки о реализации на C ++.
Вы хотите использовать Расстояние Левенштейна между двумя словами, но я предполагаю, что вы знаете это, поскольку это то, что говорят теги вопроса.
Вам нужно будет пройтись по списку (предположение) и сравнить каждое слово в списке с текущим запросом, который вы выполняете. Вы можете построить BK-дерево , чтобы ограничить пространство поиска, но это звучит как излишество, если у вас только ~ 3000 слов.
var upperLimit = 2;
var allWords = GetAllWords();
var matchingWords = allWords
.Where(word => Levenshtein(query, word) <= upperLimit)
.ToList();
Добавлено после редактирования исходного вопроса
Поиск случаев, когда расстояние = 0 будет легко Contains-query, если у вас есть нечувствительный к регистру словарь. В тех случаях, когда расстояние <= 2, потребуется полное сканирование пространства поиска, 3000 сравнений на слово запроса. Если предположить, что одинаковое количество слов запроса приведет к 9 миллионам сравнений.
Вы упомянули, что время истекает, я полагаю, у вас настроен тайм-аут? Может ли ваша скорость быть следствием плохой или медленной реализации расчета Левенштейна?
(источник: itu.edu. tr )
Приведенный выше график украден из CLiki: bk-tree
Как видно, использование bk-дерева с расстоянием редактирования <= 2 приведет к посещению только около 1% пространства поиска, но это при условии, что у вас очень большие входные данные, в их случае до полумиллиона слов. Я бы предположил, что в вашем случае такие же числа, но такое небольшое количество входных данных не вызовет особых проблем, даже если оно будет сохранено в списке / словаре.