KDS

Материал из Кафедра АСОИУ.

Перейти к: навигация, поиск
KDS
KDS
Вид KDS в трее
Вид KDS в трее
Тип Поисковик
Разработчик ZiroCorp
Группа ИВТ-х46
Написана на C++
ОС Windows
Текущая версия 2.97 — 2 ноября 2008
Лицензия Freeware
Скачать KDS.7z (11.8 Kb)
("сохранить как")

KDS (KDS — KDS Data Service) — это бесплатное программное обеспечение позволяющее пользователям операционых систем семейства Windows определять в массиве байтов количество вхождений байтов, следующих за определенной заданной последовательности байтов, с возможностью использования разряженной последовательности байтов.

Например, если искать в строке "tra-la-la" подстроку "-l" она выдаст - символ "a" встретился 2 раза.

Данное ПО разрабатывалось в рамках курсового проекта по дисциплине Информатика на тему "Поиск разряженной подстроки".

Суть работы заключалась в реализации собственной модификации алгоритма Бойера-Мура[1]

Содержание

Как с ней работать

При первом запуске нажмите на иконку программы в трее. Подсказку можно вызвать в любое время нажав по иконке. Если увидите в подсказке надпись "Далее>>", то нажмите на нее.

Шаг 1:

Выберите в появившемся окне файл (ANSI) с разряженными строками.
Структура файла такова:

  • Вначале идут строки в HEX виде.
В качестве разделителя байт можно использовать пробелы или табуляцию. Дырка (любой байт) обозначается, как "xx" [EN]. Любые остальные, не HEX символы -> нули.
Небольшой пример <как написано> -> <как прочитано>:
  11 22 33 40 -> 1122334
  11 22 33 4 -> 11 22 33 40
  1 6 A 8 D -> 10 60 A0 80 D0
  xA 2x x -> xx xx xx
  • Затем идет строка с надписью “[Text]”, причем кроме этой надписи в строке ничего недолжно быть (даже пробелов).
  • И далее идут строки обычным текстом. Дырка - "?".

Шаг 2:

Выберите в появившемся окне подопытный файл.

Шаг 3:

Идет обработка информации, ждите...

Завершающий шаг: Поиск завершен!

Осталось выбрать место хранения файла с результатами. Структура выходного файла:

  • Вначале "[<запрос>]", как его поняла программа.
  • Далее результаты поиска "<HEX значение символа>'<символ>' <количество вхождений>".
  • И наконец "Итого: <количество вхождений запроса>".

Пример

Вот пример файла с разряженными строками:

94 71 1B	CD xx71
9x 71 1B	CD xx71
x4 7x 1B	CD xx71
9x x1 1x	CD xx71
9x x1 1x xD	   xx71

xx xx 1B CD xx 71

94 71 1B	CD E971
9x 71 1B	CD E971
x4 7x 1B	CD E971
9x x1 1x	CD E971
00 00 00 00 E9

B9 53 41 xx

FE FF FF FF
FE xx FF FF
xx FF FF FF

xxx> Если достаточно долго нажимать Шифт+ФXII, то очень скоро наступит крах.

[Text]
???Н?q

В качестве подопытного файла используйте саму программу.

Примечания

  1. В статье по ссылке приводится как описание нескольких вариантов алгоритма Бойера-Мура, так и разработанные модификации, о которых вы пока нигде больше не сможете прочесть, и конечно же адаптация алгоритма под поиск разряженных строк. Причем это именно статья, а не просто описанная "голая" теория, так что советую читать от <body> до </body> :-). Из нее можно не только понять как работает алгоритм, но и как пришло в голову его создать. Статья также содержит небольшой тестик производительности и ответы на часто задаваемые вопросы.

См. также

Личные инструменты