Как найти слово из массивов символов?
Каков наилучший способ решить эту проблему:
У меня есть группа массивов с 3-4 символами внутри каждого, вот так:
{p, {a, {t, {m,
q, b, u, n,
r, c v o
s } } }
}
У меня также есть массив словарных слов.
Каков наилучший / быстрый способ найти, если массив символов может объединиться в одно из словарных слов? Например, приведенные выше массивы могут составлять слова:
"Погладить","крыса","в","к","бродяга"(смеется)
но не "нуб" или "мат"
Должен ли я пройтись по словарю, чтобы посмотреть, можно ли составить слова или получить все комбинации из букв, тогда сравните их со словарем
4 ответа
У меня был какой-то код Scrabble, поэтому я смог собрать его вместе. Словарь, который я использовал, это sowpods (267751 слов). Код ниже читает словарь как текстовый файл с одним заглавным словом в каждой строке.
Код C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;
namespace SO_6022848
{
public struct Letter
{
public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static implicit operator Letter(char c)
{
return new Letter() { Index = Chars.IndexOf(c) };
}
public int Index;
public char ToChar()
{
return Chars[Index];
}
public override string ToString()
{
return Chars[Index].ToString();
}
}
public class Trie
{
public class Node
{
public string Word;
public bool IsTerminal { get { return Word != null; } }
public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
}
public Node Root = new Node();
public Trie(string[] words)
{
for (int w = 0; w < words.Length; w++)
{
var word = words[w];
var node = Root;
for (int len = 1; len <= word.Length; len++)
{
var letter = word[len - 1];
Node next;
if (!node.Edges.TryGetValue(letter, out next))
{
next = new Node();
if (len == word.Length)
{
next.Word = word;
}
node.Edges.Add(letter, next);
}
node = next;
}
}
}
}
class Program
{
static void GenWords(Trie.Node n, HashSet<Letter>[] sets, int currentArrayIndex, List<string> wordsFound)
{
if (currentArrayIndex < sets.Length)
{
foreach (var edge in n.Edges)
{
if (sets[currentArrayIndex].Contains(edge.Key))
{
if (edge.Value.IsTerminal)
{
wordsFound.Add(edge.Value.Word);
}
GenWords(edge.Value, sets, currentArrayIndex + 1, wordsFound);
}
}
}
}
static void Main(string[] args)
{
const int minArraySize = 3;
const int maxArraySize = 4;
const int setCount = 10;
const bool generateRandomInput = true;
var trie = new Trie(File.ReadAllLines("sowpods.txt"));
var watch = new Stopwatch();
var trials = 10000;
var wordCountSum = 0;
var rand = new Random(37);
for (int t = 0; t < trials; t++)
{
HashSet<Letter>[] sets;
if (generateRandomInput)
{
sets = new HashSet<Letter>[setCount];
for (int i = 0; i < setCount; i++)
{
sets[i] = new HashSet<Letter>();
var size = minArraySize + rand.Next(maxArraySize - minArraySize + 1);
while (sets[i].Count < size)
{
sets[i].Add(Letter.Chars[rand.Next(Letter.Chars.Length)]);
}
}
}
else
{
sets = new HashSet<Letter>[] {
new HashSet<Letter>(new Letter[] { 'P', 'Q', 'R', 'S' }),
new HashSet<Letter>(new Letter[] { 'A', 'B', 'C' }),
new HashSet<Letter>(new Letter[] { 'T', 'U', 'V' }),
new HashSet<Letter>(new Letter[] { 'M', 'N', 'O' }) };
}
watch.Start();
var wordsFound = new List<string>();
for (int i = 0; i < sets.Length - 1; i++)
{
GenWords(trie.Root, sets, i, wordsFound);
}
watch.Stop();
wordCountSum += wordsFound.Count;
if (!generateRandomInput && t == 0)
{
foreach (var word in wordsFound)
{
Console.WriteLine(word);
}
}
}
Console.WriteLine("Elapsed per trial = {0}", new TimeSpan(watch.Elapsed.Ticks / trials));
Console.WriteLine("Average word count per trial = {0:0.0}", (float)wordCountSum / trials);
}
}
}
Вот вывод при использовании ваших тестовых данных:
PA
PAT
PAV
QAT
RAT
RATO
RAUN
SAT
SAU
SAV
SCUM
AT
AVO
BUM
BUN
CUM
TO
UM
UN
Elapsed per trial = 00:00:00.0000725
Average word count per trial = 19.0
И вывод при использовании случайных данных (не печатает каждое слово):
Elapsed per trial = 00:00:00.0002910
Average word count per trial = 62.2
РЕДАКТИРОВАТЬ: я сделал это намного быстрее с двумя изменениями: хранение слова в каждом терминальном узле дерева, чтобы его не пришлось перестраивать. И сохранение входных букв в виде массива хеш-наборов вместо массива массивов, так что вызов Contains() будет быстрым.
Есть, вероятно, много способов решения этой проблемы.
Что вас интересует, так это количество каждого символа, которое у вас есть для формирования слова, и сколько каждого символа требуется для каждого словарного слова. Хитрость заключается в том, как эффективно искать эту информацию в словаре.
Возможно, вы можете использовать префиксное дерево ( trie), какую-то интеллектуальную хеш-таблицу или подобное.
В любом случае, вам, вероятно, придется опробовать все свои возможности и сравнить их со словарем. Т.е., если у вас есть три массива по три значения в каждом, будет 3^3+3^2+3^1=39 комбинаций для проверки. Если этот процесс слишком медленный, то, возможно, вы могли бы вставить фильтр Блума перед словарем, чтобы быстро проверить, нет ли слова в словаре.
РЕДАКТИРОВАТЬ: В любом случае, это не то же самое, что Scrabble? Возможно, попробуйте Googling для " алгоритма скрэббл", и он даст вам хорошие подсказки.
На переформулированный вопрос можно ответить только путем генерации и тестирования. Поскольку у вас есть 4 буквы и 10 массивов, у вас есть только около 1 миллиона возможных комбинаций (10 миллионов, если вы разрешите пустой символ). Вам понадобится эффективный способ их поиска, использовать BDB или какой-нибудь хэш на основе диска.
Предыдущее опубликованное решение должно также работать, вы просто более ограничены тем, какие символы вы можете выбрать на каждом этапе поиска. Это должно быть быстрее.
Я только что сделал очень большой вложенный цикл, например:
for(NSString*s1 in [letterList objectAtIndex:0]{
for(NSString*s2 in [letterList objectAtIndex:1]{
8 more times...
}
}
Затем я делаю двоичный поиск по комбинации, чтобы увидеть, есть ли она в словаре, и добавить ее в массив, если это