Как найти строку информации

Войти на сайт

или

Забыли пароль?
Еще не зарегистрированы?

Алгоритмы поиска в строке

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска

Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)

После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)

На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск)

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.

Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

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

Найти строку по заданным параметрам

Для решения задачи поиска строк в ТЧ будем использовать функцию НайтиСтроки.

Синтаксис: НайтиСтроки(<ПараметрыОтбора>)
Параметры: <ПараметрыОтбора> (обязательный)
Тип: Структура. Задает условия поиска: ключ структуры определяет имя колонки, по которой будет осуществляться поиск, а значение структуры – искомое значение.
Возвращаемое значение: Массив из строк табличной части, соответствующих заданному условию поиска.
Замечание! Массив хранит ссылки на строки табличной части, то есть при изменении строки в табличной части, значение в массиве тоже будет изменено.
Описание: Осуществляет поиск строк табличной части, соответствующих заданному условию поиска.

Первый вариант, который встречается в работе найти строки с определенным значением в колонке.

Найти все строки ТЧ с определенным значением задачи.

1. Создадим структуру отбор и установим значение задачи
2. Применим функцию НайтиСтроки к нужной табличной части
3. В переменной МассивНайденныхСтрок будут ссылки на строки таблицы которые содержат нужную нам задачу

Отбор = Новый Структура("Задача",ДокументСсылкаЗадача);
МассивНайденныхСтрок = ТЧПодзадачи.НайтиСтроки(Отбор);

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

Найти все строки ТЧ с определенным значением номенклатуры и количества

1. Создаем структуру для отбора
2. Устанавливаем два параметра поиска (если параметров больше устанавливаем столько, сколько надо)
3. Ищем в таблице нужные строки
4. Получаем переменную МассивНайденныхСтрок с нужными данными

Отбор = Новый Структура;
Отбор.Вставить("Номенклатура",СправочникНоменклатураСсылка);
Отбор.Вставить("Количество",ИскомоеКоличество);

МассивНайденныхСтрок = РеализацияТовароУслуг.Товары.НайтиСтроки(Отбор);   

В примере номер три реализуем процедуру которая сообщит все цены номенклатуры в определенном документе.

Реализовать процедуру которая сообщит цену на товар в поступлениях, реализациях и счетах на выбор пользователя.

Порядок действий будет похож на прошлые два примера:

1. Создаем отбор и устанавливаем значения поиска
2. Ищем в табличной части
3. Сообщаем все цены которые нашли

&НаСервере
Процедура НайтиЦеныНаТовар(Документ,СправочникНоменклатураСсылка)
	Отбор = Новый Структура("Номенклатура", СправочникНоменклатураСсылка);
	МассивНайденныхСтрок = Документ["Товары"].НайтиСтроки(Отбор);
	Для Каждого ЭлМас Из  МассивНайденныхСтрок Цикл
		Сообщить(ЭлМас.Цена);
	КонецЦикла;
КонецПроцедуры   

В 1с существует метод Найти(), это устаревший метод для его не стоит использовать.

Дополнительные материалы по теме:

1. Заметки и учебные примеры по программированию у меня на сайте ищите – тут
2. Интересная статья про НайтиСтроки – тут

От автора: вы тут запись мою не видели? Выпала из базы, теперь не знаю, что и делать! Наверное, сегодня возьмемся за поиск в MySQL. А я как раз вспомню, как более эффективно просеивать данные в СУБД и заодно свою строку постараюсь найти.

Зачем просеивать?

Просеивание в MySQL – одна из самых часто выполняемых задач. Для этого в системах управления БД, поддерживающих SQL, используется команда SELECT. В предыдущих материалах мы уже сталкивались с ней, применяя ее для нахождения и вывода строк, отвечающих «простеньким» критериям сортировки. На самом деле данная команда является одной из главных, и ее возможности в сфере поиска записей почти безграничны.

При этом написание правильных запросов на выборку данных в MySQL очень часто похоже на составление заклинаний. Особенно такое впечатление складывается у новичков, которые только ступили на путь изучения СУБД. Но сегодня мы постараемся развеять это «сюрреалистическое» наваждение, и научимся составлять правильные запросы для поиска по MySQL базе.

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

Просеиваем строки через phpMyAdmin

Зайдите в программу, выберите любую БД и таблицу в ней. Я бы советовал вам использовать таблицу поменьше, в которой всего несколько срок. В них лучше видны результаты сортировки.

Выбрав слева в меню базу и таблицу, перейдите сверху в раздел «Обзор». После этого СУБД выведет все строки, которые содержатся в данной структуре. Для этого программа направила на выполнение серверу БД запрос на выборку. Его код отображается выше результатов выборки.

Ниже находится весь встроенный функционал программы для поиска по MySQL базе. Чтобы установить способ «просеивания» по первичному ключу (по убыванию или возрастанию), используется переключатель «Сортировать по индексу».

Кроме этого можно «просеять» все строки, изменив порядок вывода данных по значению каждого из столбцов (убыванию и возрастанию). Для этого нужно нажать на имя столбца вверху списка. При этом для строковых значений порядок вывода будет изменяться в алфавитном порядке.

Но весь этот функционал пригодится вам только для осуществления поиска в небольших таблицах. Для более внушительных объемов данных придется использовать SQL.

Мощные средства SQL

Как уже упоминалось, для поиска в MySQL используется команда SELECT. Ее синтаксис я приводить не буду, поскольку его размер может испугать даже самого опытного разработчика. Поэтому только на скриншоте, чтобы вы не упали в обморок :).

Будет «постигать» данную команду на примерах ее использования, которые могут пригодиться вам для построения более сложных запросов. Стартуем! Я все-таки опять «поиграюсь» со своими «зверушками», и все запросы буду адресовать таблице animal:

Находим строку по номеру id:

В этом запросе мы используем оператор WHERE, после которого задаем критерий поиска. Выводим определенные столбцы искомой строки:

В данном примере мы вывели не полностью искомую строку, а только значение столбца name. Поиск по строковому значению:

Здесь мы использовали в качестве параметра для поиска по MySQL базе строчное значение. Сортировка результатов выборки по возрастанию или убыванию:

Для сортировки результатов выборки мы использовали директиву ORDER BY. По умолчанию, установлена сортировка по возрастанию (ключевое слово ASC). Чтобы задать обратный порядок (по убыванию) нужно использовать слово DESC.

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

Углубляемся

Давайте покинем наше «зверье» и перенесемся в базу данных world. На ней я продемонстрирую еще несколько примеров выборки данных, соответствующих заданным параметрам. Все запросы я буду демонстрировать на основе таблицы country. Иногда (особенно в больших по размеру таблицах) требуется задать не один критерий для поиска, а несколько. Тогда запрос на получения списка стран из Европы и Африки будет выглядеть следующим образом:

Этот же запрос на поиск по MySQL базе можно укоротить, если использовать ключевое слово in. Например:

Для указания диапазона выборки применяется ключевое слово Between. Давайте выведем страны с численностью населения от 10 до 50 тыс. За основу возьмем предыдущий запрос:

Пример в PHP

Теперь приведем пример, как запустить поиск в PHP MySQL данных. Используем предыдущий запрос.

Ну, вроде бы я вкратце рассказал вам все о поиске в MySQL. Надеюсь, из этой статьи вы почерпнули для себя что-то новенькое. А свою строку я так и не нашел. Наверное, кот утащил, пока я отходил от компа. Ох, уж это зверье :).