Каков наилучший способ расшифровки слов с помощью PHP? - PullRequest
4 голосов
/ 15 февраля 2011

У меня есть список слов, и я хочу расшифровать слова, используя этот список слов в PHP.

Мне кажется, что в PHP нет встроенной функции, которая делает это.Так может кто-нибудь предложить хороший алгоритм, чтобы сделать это, или, по крайней мере, указать мне правильное направление?

РЕДАКТИРОВАТЬ: отредактировано, чтобы добавить пример

Итак, в основном, я говорюУ меня есть список слов:

   apple
   banana
   orange

Затем мне дают кучу перемешанных букв.

   pplea
   nanaba
   eroang

Ответы [ 7 ]

5 голосов
/ 15 февраля 2011

Имеется словарь известных слов:

foreach ($list as $word)
{
  if (count_chars($scrambled_word,1) == count_chars($word,1))
    echo "$word\n";
}

Редактировать: Простая оптимизация заключалась бы в перемещении count_chars($scrambled_word,1)) за пределы цикла, поскольку оно никогда не изменяется:

$letters = count_chars($scrambled_word,1)
foreach ($list as $word)
{
  if ($letters == count_chars($word,1))
    echo "$word\n";
}
3 голосов
/ 15 февраля 2011

Предупреждение: я редко использую PHP, поэтому он имеет дело только с общим алгоритмом, который должен работать практически на любом языке, а не чем-то специфичным для PHP.

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

Если это правильно, общая идея довольно проста: взять копию списка слов и отсортировать буквы в каждомслово в алфавитном порядке.Поместите отсортированные и несортированные версии каждого слова рядом и отсортируйте все по отсортированным словам (но сохраняя каждое несортированное слово вместе с его отсортированной версией).Возможно, вы захотите свернуть дубликаты вместе, чтобы (например) вместо {abt: bat} и {abt: tab} у вас было: {abt: bat, tab}

Затем, чтобы сопоставитьскремблируй слово, сортируй буквы в алфавитном порядке.Ищите совпадения в своем словаре (поскольку он отсортирован, вы можете использовать бинарный поиск).Когда вы найдете совпадение, результатом будет слово (или слова), связанное с этой группой отсортированных букв.Используя приведенный выше пример, если зашифрованное слово было «tba», вы бы отсортировали его, чтобы получить «abt», затем найдите «abt», чтобы получить «bat» и «tab».

Редактировать: как@ Морон указал в комментариях, сортировка и бинарный поиск не являются по сути важными моментами сами по себе.Основные пункты - превратить все эквивалентные входные данные в идентичные ключи, а затем использовать какой-то быстрый поиск по ключу, чтобы найти слово (а) для этого ключа.

Сортировка букв в каждом слове - это простой способ превратить эквивалентные вводы в идентичные клавиши.Сортировка списка и выполнение двоичного поиска - один из простых способов быстрого поиска по ключу.

В обоих случаях существует довольно много альтернатив.Я совсем не уверен, что альтернативы могут значительно улучшить производительность, но они, безусловно, могли бы.

Например, вместо простого бинарного поиска вы могли бы иметь второй уровень индекса, который говорит вам, гдеклавиши, начинающиеся с «а», были клавиши, начинающиеся с «б», и так далее.Учитывая, что несколько чрезвычайно часто используемых букв находятся в начале алфавита (например, 'e' и 'a'), вам может лучше отсортировать слова так, чтобы относительно необычные буквы ('q ',' z 'и т. д.) направлены к передней части клавиши, а наиболее часто используемые буквы - в конце.Это дало бы первому поиску, основанному на начальном символе, наибольшую дискриминацию.

Что касается сортировки / бинарного поиска, возможно, существует больше альтернатив и, вероятно, более убедительные аргументы в пользу использования чего-то еще.Хеш-таблицы обычно разрешают поиск в (почти) постоянном времени.Попытки могут существенно сократить объем памяти, особенно когда многие слова имеют общий префикс.Единственным очевидным недостатком является то, что код для любого из них, вероятно, является более трудоемким (хотя тип массива PHP основан на хэше, так что вы, вероятно, могли бы использовать его довольно хорошо).

1 голос
/ 15 ноября 2015

Можно расшифровать в O(log p + n), где

p = size of dictionary 
n = length of word to be unscrambled

Предположим, что константа, c, большинство вхождений какой-либо буквы в любом слове плюс 1.
Предположим, константа k, количество букв в алфавите.
Допустим, константа, j, наибольшее количество слов, которые могут использовать один и тот же хэш или отсортированную по буквам версию.

Инициализация O(p) пробела:
1. Используя словарь, D, создайте связанный список отсортированных по буквам слов, L, который будет иметь размер не более p, поскольку каждыйСлово имеет одну отсортированную версию.
2. Свяжите другой столбец с L с числовым хешем целых чисел, который может варьироваться в диапазоне [0, c^k-1].3. Для каждого слова в L сгенерируйте его хэш с помощью следующей функции:
hash(word) = 0 if word is empty or (c^i + hash(remaining substring of the word))
, где i - это алфавитный индекс первой буквы.

Алгоритм:
1. В O(n) определите хэш h версии отсортированного по буквам слова, о котором идет речь.
2. В O(log p) найдите хэш в L.
3. В O(n) список j связанных слов длиной n.

0 голосов
/ 15 февраля 2011

Если у вас действительно большой список слов и вы хотите, чтобы эта операция расшифровки была быстрой, я бы попытался поместить список слов в базу данных.Затем добавьте поле в таблицу списка слов, которое является суммой значений ascii слова, а затем добавьте индекс этой суммы ascii.

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

Пример данных предполагает все строчные буквы (a= 97, b = 98, c = 99, ...) bat => 311, cat => 312, ...

Пример функции php для определения суммы для слова

function asciiSum($word) {
  $characters = str_split(strtolower($word));
  $sum = 0;
  foreach($characters as $character) {
    $sum += ord($character);
  }
  return $sum;
}

Еще быстрее: добавьте еще одно поле в базу данных, которое представляет длину строки, затем вы можете искать слова на основе суммы ASCII и длины строки, что еще больше уменьшит количество ложных совпадений, которые вам нужно будет проверить.

0 голосов
/ 15 февраля 2011

Используйте функции массива PHP, поскольку они могут решить эту проблему за вас.

$words = array('hello', 'food', 'stuff', 'happy', 'fast');
$scrambled_word = 'oehll';

foreach ($words as $word)
{
    // Same length?
    if (strlen($scrambled_word) === strlen($word))
    {
        // Convert to an array and match
        if( ! array_diff(str_split($word), str_split($scrambled_word)))
        {
            print "Your word is: $word";
        }
    }
}

По сути, вы ищете что-то одинаковой длины, а затем просите PHP проверить, все ли буквы одинаковы.

0 голосов
/ 15 февраля 2011

Медленным вариантом будет генерировать все перестановки букв в зашифрованном слове, а затем проверять их с помощью pspell_check () .

Если, однако, вы можете использовать текстовый файл необработанного словаря, то лучшим вариантом будет просто использовать регулярное выражение для его сканирования:

$dict = file_get_contents("words.txt");  // one word per line

$n = strlen($word);
if (preg_match('/^[$word]{$n}$/im', $dict, $match)) {
    print $match[0];
}

Я совершенно уверен, что PCRE значительно быстрее в поиске перестановок, чем PHP и метод угадывания.

0 голосов
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...