Как я могу ускорить этот алгоритм анаграммы

Question

Я делаю мобильное приложение для поиска анаграмм и частичных совпадений. Мобильность важна, потому что вычислительная мощность невелика, а эффективность является ключевым фактором.

Алгоритм принимает любое количество букв, включая повторы, и находит самые длинные слова, составленные из его букв, используя каждую букву только один раз. Я также заинтересован в быстром нахождении лучших результатов, и на самом деле меня не интересуют днища (более короткие), пока N встречается. Например:

STACK => stack, tacks, acts, cask, cast, cats…

Я немного погуглил и нашел несколько алгоритмов, и я нашел один, который, как мне показалось, будет эффективным, но не настолько эффективным, как хотелось бы.

У меня есть готовый словарь поиска, который сопоставляет отсортированный ключ с реальными словами, которые генерируют этот ключ.

"aelpp" => ["apple", "appel", "pepla"]

Далее я разбил каждый словарь на разные по длине ключа. Таким образом, ключи длиной 5 букв находятся в одном словаре, а ключи длиной 6 - в другом. Каждый из этих словарей находится в массиве, в котором индекс - это длина ключей, найденных в словаре.

anagramArray[5] => dictionary5
dictionary5["aelpp"] => ["apple", "appel", "pepla"]

Мой алгоритм начинается с ввода входного слова "lappe" и сортирует его:

"lappe" => "aelpp"

Теперь для каждого словаря, содержащего не более 5 букв, я делаю сравнение, чтобы вытащить его. Вот псевдокод:

word = input.sort
for (i = word.length; i > 0; i--)
    dictionaryN = array[i]
    for (key in dictionaryN)
        if word matches key
            add to returnArray
        end
    end
    if returnArray count > N
      break
    end
end

returnArray.sort by longest word, alphabetize

В словаре всего около 170 000 слов, но поиск занимает 12 секунд для 12-буквенного ввода. Мой метод match делает регулярное выражение из ключа:

"ackst" => /a.*c.*k.*s.*t.*/

, например 4-буквенный ключ, например acst (действует), будет соответствовать ackst (стек), поскольку:

"ackst" matches /a.*c.*s.*t.*/

Я видел, как другие приложения делают то же самое за гораздо меньшее время, и мне интересно, является ли мой подход ненужным или просто нуждается в настройке.

Как получить максимальную вычислительную эффективность для генерации лучших N анаграмм из слова, отсортированного по максимальной длине?

Answer 1

Если вы думаете (и, возможно, даже представляете) словарь как дерево букв, вы можете избежать просмотра множества узлов. Если в словаре есть «стек», то путь от корня к листу будет обозначен как a-c-k-s-t. Если входное слово «атаки», тогда сортируйте это, чтобы получить aackstt. Вы можете написать рекурсивную подпрограмму, которая будет следовать ссылкам вниз от корня, потребляя письма от aackstt по ходу работы. Когда вы достигнете ack, у вас останется stt в вашей строке, так что вы можете следовать за s, чтобы достичь ackst, но вы можете исключить следующие u для достижения acku и его потомков, v для достижения ackv и его потомков и т. Д.

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

Answer 2

O (N) Время и O (1) решение, чтобы проверить, являются ли 2 строки анаграммами

bool Anagram( const  char *s1, const char *s2)
{
    unsigned int sum=0;

    if ( s1 == NULL || s2 == NULL)
        return false;

    while ( *s1 != '\0' && s2 != '\0')
    {
                   sum ^= *s1;
                   sum ^= *s2;
                   s1++;
                   s2++;
    }

    if ( s1 != '\0' || s2 != '\0')
        return false;

    if (sum) return false;

    return true;
}

Если вы xor два равных числа .. ваш результат равен 0. (следовательно, алгоритм)

Answer 3

Это просто идея, но, возможно, это то, что вы ищете. У вас есть только одна структура, которую вы перебираете, и в ней есть все слова всех размеров. На каждом шаге итерации вы вводите еще одну букву и ограничиваете поиск только теми словами, которые не имеют букв «больше», чем уже введенные. Например, если вы введете M, вы больше не сможете вводить что-либо в диапазоне N-Z.

Структура может быть бинарным деревом, где введение одной буквы ведет вас на несколько уровней дерева дальше. У каждого узла есть буква, и ветвь с остальными меньшими буквами, и ветвь с остальными большими буквами, и ветвь с корнем следующего суженного поиска, и указатель на список слов, которые полностью составлены из букв введено до сих пор. Ветви могут быть нулевыми, если в этом подпространстве поиска нет возможных слов, но вы не можете одновременно иметь нулевое значение для 3 ветвей и нулевое значение для указателя на список слов. (Ну, вы можете, как своего рода оптимизация, которая сейчас неактуальна). Вместо указателя на список слов у вас может быть флаг, обозначающий наличие слов с заданными буквами, но эти слова могут быть сохранены в каком-то другом словаре.

Итак, скажем, у нас есть буквы ACKST. В корне структуры вы ищете все эти буквы в цикле, но после K, например, вы можете продолжить поиск только с A и C (так как S и T выше K). Поскольку нас больше всего интересует наибольшее слово, мы должны начать поиск с самой большой буквы (в данном случае T) и продолжить ее со следующей самой большой буквы. К слову CAT мы можем только искать буквы T, C, A в указанном порядке. Как только мы дойдем до A, появится указатель на список следующих слов: ACT, CAT.

Answer 4

Создайте свой словарь следующим образом:

 For each word W in the English language (or whatever word set you have)

     Sort the characters in W by alphabetical order (e.g. "apple" -> "aelpp") into a new string called W'

     Compute Hash H into W' using any fast hash algorithm (e.g CRC32.  You could likely invent anything yourself that has a low number of collisions)

     Store W and H as an element in the dictionary array
     That is:
        Word.original = W;
        Word.hash = Hash(W');
        Dictionary.append(Word);

  Sort the dictionary by hash values.

А теперь, чтобы найти все анаграммы или слово для поиска S

  Sort the characters in S by alphabetical order (e.g. "apple" -> "aelpp") into a new string called S'

  Compute Hash H of S' using the same fast hash algorithm above

  Now do a binary search on the dictionary for H.  The binary search should return an index F into Dictionary

  If the binary search fails to return an index into the Dictionary array, exit and return nothing

  I = F

  // Scan forward in the dictionary array looking for matches
  // a matching hash value is not a guarantee of an anagram match
  while (I < Dictionary.size) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)

  // Scan backwards in the dictionary array looking for matches
  I = F-1;
  while (I >= 0) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)


  return ResultSet     

Теперь я не рассматривал, как обрабатывать «подстроку»поиск (поиск слов анаграммы, которые меньше по длине, чем искомое слово. Я был немного смущен, если это было требованием. Ваши инструкции подразумевают, что этот повторяющийся набор анаграмм должен иметь точно такой же набор символов, что и искомое слово. НоСкорее всего, вы можете перечислить все подстроки в строке поиска и выполнить каждую подстроку с помощью алгоритма поиска, описанного выше.

Answer 5

Создание регулярных выражений немного дорого, и поэтому вы, вероятно, не хотите делать это внутри цикла.

Опция (не обязательно сверхэффективная, но, кажется, полезная в данном конкретном случае), которая приходит на ум, заключается в том, что вместо поиска по всем вашим словам в словаре, попробуйте удалить буквы в различных комбинациях и проверить, если результат Строка в вашем словаре. Это будет максимально до 2 ^ n итераций (где n - количество букв в вашем слове), что лучше, чем 170k для n <18. Обратите внимание, что этот конкретный подход не подходит для длинных входов, но он должен быть в противном случае очень быстро. </p>