Лучший способ поиска 8-символьной строки для слов в AS3?

Question

Я извиняюсь перед тем, как ответить на этот вопрос, но я посмотрел и не смог найти именно то, что искал.

Я ищу лучший способ поиска строки из 8 символовв AS3, чтобы увидеть, содержит ли он слово или слова.У меня уже есть словарь слов, загруженных во Flash, с ...

[Embed(source = "../f-16.txt",mimeType = "application/octet-stream")]
private static const wordFile:Class;
var words:Array = new wordFile().toString().split("\n");

Я думал разбить это далее на 26 массивов для каждой начальной буквы, а затем, возможно, эти массивы на массивыслов различной длины (так что все 8-буквенные слова, начинающиеся с a, вместе и т. д.)

Что мне нужно сделать, это найти строку из 8 символов в AS3, чтобы увидеть, содержит ли она какое-либо слово или словаиз словарного массива.Ниже приведены примеры строк и то, что мне нужно вернуть ...

1. "beenpoet" = "бывало", "поэт"
2. "itxitxit" = "это", "это"," это "
3. " aardvark "=" aardvark "

и так далее.Проблема, которую я вижу, состоит в том, что слова могут начинаться в любой точке строки, что усложняет дело.

Каков наилучший (самый быстрый) способ сделать это в as3?

Спасибо за любыепомощь.

Answer 1

я ...

Я немного пьян. (Это может быть удалено SO модами.) (Edit: я очень пьян.)

Однако, для вашего конкретного случая использования ....

Я ищу лучший способ поиска 8-символьной строки в AS3, чтобы увидеть если оно содержит слово или слова. У меня уже есть словарь слов загружается во Flash, с ...

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

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

Каждый символ вашей строки будет слоем вашего дерева. В идеале вы сможете хорошо остановиться до того, как достигнете максимальной ветви. Ваш максимальный поиск будет 26 ^ 8, независимо от того, что это число.

Лучшее в этом подходе состоит в том, что с древовидной структурой повторение вдоль дерева должно быть тривиальным с точки зрения написания кода. Вам нужно только хранить слова словаря. Таким образом, если кто-то введет «cbyir», вы узнаете (по второму символу), что ввод не соответствует словарному слову. (Если только нет слова, начинающегося с CB. О Вебстер, где ты?)

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

Опять же, я пьян. Я желаю вам удачи! :-D Если у вас есть какие-либо вопросы, пожалуйста, прокомментируйте, так как я знаю, что это может быть не ясно.

Редактировать: я вернулся к этому ответу, потому что я думал об этом. Возможная реализация может использовать класс словаря AS3; Вы можете иметь словари, указывающие на словари. Это будет намного быстрее, чем поиск в массиве, так как время поиска для словарей составляет O (1). Это означает, что поиск в вашем дереве будет действительно, действительно быстрым - количество итераций будет равно количеству букв в вашем слове, а не количеству возможных комбинаций букв в вашем слове.

Дайте что-то вроде этого; Я уверен, что это сработает. Если у вас есть вопросы по реализации, дайте мне знать.

Answer 2

Вот что вам нужно сделать:

public function verifyWord(word : String, wordList : Array) : Array
{
    var resultArray : Array = [];
    for(var i : int = 0; i < word.length; i++)
    {
        for(var j : int = word.length; j > i; j--)
        {
            var brokenWord : String = word.substring(i, j);
            if(wordList.indexOf(brokenWord) >= 0)  // We are performing a search on a array, so its O(n), super slow, change this for something good
            {
                resultArray.push(brokenWord);
            }
        }
    }
    return resultArray;
}

В основном:

• Разбить входное слово на все возможные комбинации;

• Для каждого разбитого слова вам необходимо проверить, есть ли в словаре их (в настоящее время используется поиск по массиву, который является МЕДЛЕННЫМ);

• Чтобы повысить производительность, вы можете либо сохранить словарь в качестве хеш-таблицы, либо использовать полуинтервальный или более интеллектуальный алгоритм поиска, чтобы проверить, находится слово в словаре или нет (см. AS3: Большой текст файлы с indexOf () в массиве )

Answer 3

Как насчет этого:

public class WordFinder {

   public var searchFor:Array = [];

   public function search(value:String):Array {
      var result:Array=[];
      for each (var word:String in searchFor) {
         if (value.indexOf(word) >= 0) {
            result.push(word);
         }
      }
   }
}