Алгоритм для нескольких слово, соответствующее в тексте
Получение общего количества результатов и разбиения на страницы является двумя различными операциями. Ради этого примера давайте предположим, что запрос, с которым Вы имеете дело,
SELECT * FROM Orders WHERE OrderDate >= '1980-01-01' ORDER BY OrderDate
В этом случае, Вы определили бы общее количество использования результатов:
SELECT COUNT(*) FROM Orders WHERE OrderDate >= '1980-01-01'
..., который может казаться неэффективным, но на самом деле довольно производителен, принимая все индексы и т.д., правильно настраиваются.
затем для возвращения фактических результатов разбитым на страницы способом следующий запрос был бы самым эффективным:
SELECT *
FROM ( SELECT ROW_NUMBER() OVER ( ORDER BY OrderDate ) AS RowNum, *
FROM Orders
WHERE OrderDate >= '1980-01-01'
) AS RowConstrainedResult
WHERE RowNum >= 1
AND RowNum < 20
ORDER BY RowNum
Это возвратит строки 1-19 из исходного запроса. Прохладная вещь здесь, специально для веб-приложений, состоит в том, что Вы не должны сохранять состояние, кроме номеров строк, которые будут возвращены.
6 ответов
input the 10,000 words into a hashtable then check each of the words in the block of text if its hash has an entry.
Faster though I don't know, just another method (would depend on how many words you are searching for).
simple perl examp:
my $word_block = "the guy went afk after being popped by a brownrabbit";
my %hash = ();
my @words = split /\s/, $word_block;
while(<DATA>) { chomp; $hash{$_} = 1; }
foreach $word (@words)
{
print "found word: $word\n" if exists $hash{$word};
}
__DATA__
afk
lol
brownrabbit
popped
garbage
trash
sitdown
Попробуйте алгоритм Ахо-Корасика: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm
Создайте дерево своих слов, а затем используйте его, чтобы найти слова в тексте.
Строковый алгоритм Бойера-Мура должен работать. в зависимости от размера / # или слов в блоке текста вы можете использовать его в качестве ключа для поиска в списке слов (в списке больше слов, чем в блоке). Кроме того, вы, вероятно, захотите удалить любые дубли из обоих списков.
вы можете построить граф, используемый в качестве конечного автомата, и когда вы обрабатываете i-й символ вашего входного слова - Ci - вы пытаетесь перейти на i-й уровень вашего графа, проверяя, были ли ваши предыдущие узел, связанный с Ci-1, имеет дочерний узел, связанный с Ci
например: если в вашем корпусе есть следующие слова
(«искусство», «есть», «быть», «пчела»)
в вашем графике будут следующие узлы
n11 = "а"
n21 = "г"
n11.sons = (n21)
n31 = 'e'
n32 = "t"
n21.sons = (n31, n32)
n41 = 'art' (здесь у нас есть лист в нашем графике, и слово build из всех верхних узлов связано с этим узлом)
n31.sons = (n41)
n42 = 'are' (здесь снова есть слово)
n32.sons = (n42)
n12 = 'b'
n22 = 'e'
n12.sons = (n22)
n33 = 'e'
n34 = "быть" (слово)
n22.sons = (n33, n34)
n43 = 'bee' (word)
n33.sons = (n43)
во время вашего процесса, если вы проходите лист во время обработки последнего символа вашего входного слова, и только в этом случае , это означает, что ваш ввод находится в вашем корпусе.
Этот метод сложнее реализовать, чем один словарь или хеш-таблицу, но он будет намного более оптимизирован с точки зрения использования памяти
Ответ во многом зависит от реальных требований.
- Насколько велик список слов?
- Насколько велик текстовый блок?
- Сколько текстовых блоков необходимо обработать?
- Как часто нужно обрабатывать каждый текстовый блок?
- Меняются ли текстовые блоки или список слов? Если, как часто?
Предполагая, что текстовые блоки относительно небольшие по сравнению со списком слов и обрабатывая каждый текстовый блок только один раз, я предлагаю поместить слова из списка слов в хеш-таблицу. Затем вы можете выполнить поиск по хэшу для каждого слова в текстовом блоке и выяснить, содержит ли это слово список слов.
Если вам нужно обрабатывать текстовые блоки несколько раз, я предлагаю инвертировать текстовые блоки. Инвертирование текстового блока означает создание списка для каждого слова, содержащего все текстовые блоки, содержащие определенное слово.