Улучшение ввода (информатика)
В информатике — это принцип , улучшение входных данных согласно которому обработка данных входных данных для решения проблемы и их изменение определенным образом повысят эффективность выполнения или экономию пространства , или и то, и другое. Измененные входные данные обычно сохраняются и доступны для упрощения проблемы. Используя структуру и свойства входных данных, улучшение входных данных обеспечивает различное повышение эффективности алгоритма .
Идет поиск
[ редактировать ]Улучшение ввода при поиске уже некоторое время является важным компонентом мира алгоритмов в информатике. Основная идея этого принципа заключается в том, что эффективность поиска намного выше, если уходит время на создание или сортировку структуры данных перед попыткой поиска элемента в указанной структуре данных данного ввода.
Предварительная сортировка
[ редактировать ]Предварительная сортировка — это метод сортировки входных данных перед попыткой их поиска. Поскольку добавление компонента сортировки в алгоритм добавляется к времени выполнения алгоритма поиска, а не умножается, оно конкурирует только за самую медленную часть алгоритма. Поскольку эффективность алгоритмов измеряется самым медленным компонентом, добавление компонента сортировки незначительно, если поиск менее эффективен. К сожалению, предварительная сортировка обычно является самым медленным компонентом алгоритма. Напротив, алгоритм поиска без предварительной сортировки почти всегда медленнее, чем с предварительной сортировкой.
Сортировочная часть алгоритма обрабатывает входные данные задачи еще до того, как достигается поисковая часть алгоритма. Наличие сортировки элементов входных данных в определенном порядке делает поиск на практике тривиальным. Простейшие алгоритмы сортировки — сортировка вставкой , сортировка выбором и пузырьковая сортировка — имеют время выполнения наихудшего случая O( n 2 ), в то время как более продвинутые алгоритмы сортировки – пирамидальная сортировка , сортировка слиянием – которые имеют наихудшее время выполнения O( n log n ) – и быстрая сортировка – которая имеет наихудший случай O( n 2 ), но почти всегда равно O( n log n ). Используя эти алгоритмы сортировки, алгоритм поиска, включающий предварительную сортировку, обеспечит такую высокую эффективность.
Простой пример преимуществ предварительной сортировки можно увидеть на примере алгоритма, который проверяет массив на наличие уникальных элементов: если задан массив из n элементов, верните true, если каждый элемент массива уникален, в противном случае верните false. Псевдокод : представлен ниже
algorithm uniqueElementSearch(A[0...n]) is
for i := 0 to n – 1 do
for j := i + 1 to n do
if A[i] = A[j] then
return false
return true
Без предварительной сортировки в худшем случае этот алгоритм потребовал бы проверки каждого элемента на соответствие каждому другому элементу с двумя возможными результатами: либо в массиве нет повторяющегося элемента, либо последние два элемента в массиве являются дубликатами. Это приводит к O( n 2 ) эффективность.
Теперь сравните это с аналогичным алгоритмом, использующим предварительную сортировку. Этот алгоритм сортирует введенный массив, а затем проверяет каждую пару элементов на наличие дубликатов. Псевдокод представлен ниже:
algorithm presortUniqueElementSearch(A[0...n]) is
sort(A[0...n])
for i := 0 to n – 1 do
if A[i] = A[i + 1] then
return false
return true
Как говорилось ранее, наименее эффективной частью этого алгоритма является сортировка массива, которая, если выбрана эффективная сортировка, будет выполняться за O( n log n ). Но после того, как массив отсортирован, его нужно пройти только один раз, что займет O( n ). Это приводит к эффективности O( n log n ).
Этот простой пример демонстрирует возможности такого метода улучшения входных данных, как предварительная сортировка. Алгоритм перешел от квадратичного времени выполнения к линейному времени выполнения, что приведет к увеличению скорости обработки больших входных данных.
На деревьях
[ редактировать ]Создание структур данных для более эффективного поиска в данных также является формой улучшения ввода. Размещение данных в дереве для хранения и поиска по входным данным — еще один популярный метод. Деревья используются в информатике, и множество различных типов деревьев — деревья двоичного поиска , деревья AVL , красно-черные деревья и 2–3 дерева , и это лишь некоторые из них — были разработаны для правильного хранения, доступа и манипулирования данными, в то время как сохраняя свою структуру. Деревья — это основная структура данных для реализации словаря.
Преимущества размещения данных в дереве огромны, особенно если данные подвергаются манипулированию или многократному поиску. Двоичные деревья поиска — самый простой, но наиболее распространенный тип дерева для этой реализации. Вставка, удаление и поиск элементов в дереве выполняются в худшем случае за O( n ), но чаще всего выполняются за O(log n ). Это делает повторный поиск элементов еще быстрее для больших входных данных. Существует множество различных типов двоичных деревьев поиска, которые работают более эффективно и даже самобалансируются при добавлении и удалении элементов, например дерево AVL, которое имеет наихудший случай O(log n ) для всех операций поиска, вставки и удаления.
Потратив время на помещение введенных данных в такую структуру, вы значительно ускорите повторный поиск элементов, в отличие от поиска по необработанным данным.
Сопоставление строк
[ редактировать ]Сопоставление строк является сложной проблемой в мире программирования сейчас, когда поисковые системы находятся на переднем крае Интернета и онлайн-мира. Если задано ключевое слово или строка, которую нужно искать среди миллионов и миллионов слов, потребуется невероятное количество времени, чтобы сопоставить символ этой строки с каждым символом. Улучшение ввода позволяет изменить ввод, чтобы сделать этот процесс намного быстрее.
Алгоритм грубой силы для этой задачи будет работать следующим образом: При представлении строки из n символов, часто называемой ключом или шаблоном, строка будет сравниваться с каждым отдельным символом более длинной строки m , часто называемой текстом. Если встречается совпадающий символ, он проверяет второй символ ключа, чтобы увидеть, соответствует ли он. Если это так, проверяется следующий символ и так далее, пока строка не совпадет или последующий символ не совпадет, и вся клавиша не сдвинется на один символ. Это продолжается до тех пор, пока ключ не будет найден или пока текст не будет исчерпан.
Этот алгоритм крайне неэффективен. Максимальное количество проверочных испытаний будет составлять m - n +1, что в худшем случае составит O( mn ). В среднем случае максимальное количество проверочных попыток никогда не будет достигнуто, и будут выполнены только несколько, что приведет к средней эффективности времени O( m + n ).
Из-за необходимости более эффективных алгоритмов сопоставления строк было разработано несколько более быстрых алгоритмов, большинство из которых используют идею улучшения входных данных. Ключ предварительно обрабатывается для сбора информации о том, что искать в тексте, и эта информация сохраняется, чтобы при необходимости можно было к ней вернуться. Доступ к этой информации осуществляется за постоянное время и значительно повышает эффективность работы алгоритмов, которые ее используют, наиболее известных из которых — алгоритм Кнута-Морриса-Пратта и алгоритм Бойера-Мура . Эти алгоритмы, по большей части, используют одни и те же методы для достижения эффективности, основное различие заключается в том, как составляется ключ.
Алгоритм Хорспула
[ редактировать ]В качестве демонстрации улучшения входных данных при сопоставлении строк следует рассмотреть упрощенную версию алгоритма Бойера-Мура, алгоритм Хорспула . Алгоритм начинается с n- го символа текста m и сравнивает этот символ. Назовем этого персонажа x . Есть 4 возможных случая того, что может произойти дальше.
Случай 1 : Первый возможный случай: символа x нет в ключе. Если это произойдет, весь ключ может быть смещен на длину ключа.
Случай 2 : Второй возможный случай — символ x не является текущим символом, но x находится в ключе. В этом случае клавиша смещается, чтобы выровнять крайнее правое вхождение символа x .
Случай 3 : Третий возможный случай: символ x соответствует последнему символу ключа, но другие символы не полностью соответствуют ключу, и x больше не встречается в ключе. Если это произойдет, весь ключ может быть смещен на длину ключа.
Случай 4 : Четвертый и последний возможный случай: символ x соответствует ключу, но другие символы не полностью соответствуют ключу, и x снова встречается в ключе. В этом случае клавиша смещается, чтобы выровнять крайнее правое вхождение символа x .
Может показаться, что он не более эффективен, чем алгоритм грубой силы, поскольку при каждой проверке ему приходится проверять все символы. Однако это не так. Алгоритм Хорспула использует таблицу сдвига для хранения количества символов, которые алгоритм должен сдвинуть, если встретит определенный символ. Ввод предварительно вычисляется в таблицу со всеми возможными символами, которые могут встретиться в тексте. Размер сдвига вычисляется с двумя вариантами: первый, если символ находится не в ключе, тогда размер сдвига равен n , длине ключа; или два, если символ появляется в ключе, то значение его сдвига равно расстоянию от крайнего правого вхождения символа в первых n -1 символах ключа. Алгоритму генератора таблицы сдвигов предоставляется ключ и алфавит возможных символов, которые могут появиться в строке (K[0... n -1]) в качестве входных данных, и он возвращает таблицу сдвигов (T[0... s -1]). Псевдокод для генератора таблицы смен и пример таблицы смен для строки «POTATO» показаны ниже:
algorithm shiftTableGenerator(K[0...n-1]) is
for i = 0 to s – 1 do
T[i] := m
for j := 0 to n – 2 do
T[P[j]] := n – 1 – j
return T
| персонаж х | А | Б | С | ... | ТО | П | ... | Т | ... | С | _ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| значение сдвига | 2 | 6 | 6 | 6 | 4 | 5 | 6 | 1 | 6 | 6 | 6 |
После того, как таблица сдвигов построена на этапе улучшения ввода, алгоритм выстраивает ключ и начинает выполнение. Алгоритм выполняется до тех пор, пока не будет найдена соответствующая подстрока текста m или пока ключ не перекроет последние символы текста m . Если алгоритм обнаруживает пару несовпадающих символов, он обращается к таблице значений сдвига символов и выполняет соответствующие сдвиги. Алгоритм Хорспула берет ключ (K[0... n -1]) и текст (M[0... m -1]) и выводит либо индекс соответствующей подстроки, либо строку «Ключ не найден» в зависимости от по результату. Псевдокод алгоритма Хорспула представлен ниже:
algorithm HorspoolsAlgorithm(K[0...n-1]), M[0...m-1]) is
shiftTableGenerator(K[0...n-1])
i := n – 1
while i ≤ m – 1 do
k := 0
while k ≤ m – 1 and K[n – 1 – k] = M[i – k] do
k := k + 1
if k = m then
return i – n + 1
else
i = i + T[M[i]]
return “Key not found”
Хотя это может быть неочевидно, наихудшая эффективность этого алгоритма во время выполнения равна O( mn ). К счастью, для случайных текстов эффективность выполнения линейна, O( n/m ). Это ставит алгоритм Хорспула, который использует улучшение входных данных, в гораздо более быстрый класс, чем алгоритм грубой силы для этой задачи.
Связанные понятия
[ редактировать ]Улучшение входных данных часто используется взаимозаменяемо с предварительными вычислениями и предварительной обработкой . Несмотря на то, что они родственны, необходимо отметить несколько важных отличий.
- Предварительные вычисления и улучшение входных данных иногда можно использовать как синонимы. Более конкретно, предварительные вычисления — это вычисление заданных входных данных до того, как с входными данными будет выполнено что-либо еще. Часто создается таблица, которую можно просмотреть во время фактического выполнения алгоритма. Улучшение ввода, которое вычисляет значения и присваивает их элементам ввода, можно классифицировать как предварительные вычисления, но на этом сходство заканчивается. Существуют разделы улучшения ввода, в которых не используются предварительные вычисления, и эти термины не следует использовать одновременно.
- Говоря об изменении входных данных, предварительную обработку часто используют неправильно. В информатике препроцессор и предварительная обработка — это совершенно разные вещи. Когда предварительная обработка используется в контексте, обычно целью является изобразить концепцию улучшения ввода, а не концепцию использования препроцессора. Реализация препроцессора — это концепция, в которой программа принимает входные данные и обрабатывает их в выходные данные, которые полностью используются другой программой. Это похоже на улучшение ввода, но применение препроцессора применимо к общей программе, которая обрабатывает исходные входные данные для вывода в формате, который компилятор может прочитать и затем скомпилировать.
Ссылки
[ редактировать ]- Левитин, Анани (2012). Введение в разработку и анализ алгоритмов (третье издание). Пирсон. ISBN 978-0-13-231681-1
- Себеста, Роберт В. (2012). Концепции языков программирования (десятое издание). Пирсон. ISBN 978-0-13-139531-2