Найти наиболее частых Заказал пару слов в документе

Question

Это проблема с С. Skiena книжного, постановка задачи является:

Дайте алгоритм для нахождения пары упорядоченного слово (например, «Нью-Йорк») , встречающихся с наибольшей частотой на данной веб-странице. Какую структуру данных вы бы использовали? Оптимизируйте время и пространство.

Одно очевидное решение вставляя каждую упорядоченную пару в хэш-карте, а затем перебирает все из них, чтобы найти наиболее часто один, однако, безусловно, должно быть лучше, кто может предложить что-нибудь?

Answer 1

Я думаю, что первое, что нужно отметить, это то, что найти наиболее часто встречающуюся парную пару слов не более (или менее) трудно, чем найти наиболее частое слово. Единственное различие заключается в том, что вместо слов, составленных из букв a..z + AZ, разделенных пунктуацией или пробелами, вы ищете словарные пары, состоящие из букв a..z + A..Z + exact_one_space, аналогично разделенных пунктуацией или пробелами.

Если ваша веб-страница имеет n слов, то есть только n-1 слово-пары. Таким образом, хэширование каждой пары слов, итерация по хэш-таблице будет O (n) как во времени, так и в памяти. Это должно быть довольно быстро сделать, даже если n ~ 10^6 (т. Е. Длина среднего романа). Я не могу представить ничего более эффективного, если n не будет достаточно небольшим, и в этом случае экономия памяти, возникающая в результате построения упорядоченного списка пар слов (вместо хеш-таблицы), может перевесить стоимость увеличения сложности времени до O (nlogn)

Answer 2

Почему бы не сохранить все упорядоченные пары в дереве AVL с массивом из 10 элементов, чтобы отслеживать 10 упорядоченных пар. В AVL мы будем хранить все пары ордеров со своим счетчиком, а верхняя 10 будет храниться в массиве. таким образом, поиск любой упорядоченной пары будет O (log N), а перемещение будет O (N).

Answer 3

Я думаю, что мы не могли бы сделать лучше, чем O (n) с точки зрения времени, так как нужно было бы увидеть по крайней мере каждый элемент один раз. Таким образом, сложность времени не может быть оптимизирована дальше.

Но мы можем использовать trie для оптимизации используемого пространства. На странице часто повторяются слова, поэтому это может привести к значительному сокращению использования пространства. Листовые узлы в trie cold сохраняют частоту упорядоченной пары и используют два указателя для итерации в тексте, где один будет указывать на текущее слово, а второй - на предыдущее слово.