Улучшение ввода (информатика) - Input enhancement (computer science)

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

Поиск

Улучшение вводимых данных при поиске было важным компонентом мира алгоритмов в течение некоторого времени в информатике. Основная идея, лежащая в основе этого принципа, заключается в том, что эффективность поиска намного выше, если на создание или сортировку структура данных заданного ввода перед попыткой поиска элемента в указанной структуре данных.

Предварительная сортировка

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

Сортировочная часть алгоритма обрабатывает входные данные задачи до того, как поисковая часть алгоритма даже будет достигнута. Сортировка элементов ввода в некотором порядке делает поиск на практике тривиальным. Самые простые алгоритмы сортировки - вставка сортировки, сортировка выбора, и пузырьковая сортировка - у всех наихудшее время выполнения O (п²), а более продвинутые алгоритмы сортировки - heapsort, Сортировка слиянием - которые имеют время выполнения в худшем случае O (п бревно п) - и быстрая сортировка - в худшем случае O (п²), но почти всегда O (п бревно п). Используя эти алгоритмы сортировки, алгоритм поиска, который включает предварительную сортировку, даст следующие большой-O эффективность.

Простой пример преимуществ предварительной сортировки можно увидеть с помощью алгоритма, который проверяет массив на наличие уникальных элементов: Если массив п elements, вернуть true, если каждый элемент в массиве уникален, иначе вернуть false. В псевдокод представлен ниже:

алгоритм uniqueElementSearch (A [0 ...п]) является    за я := 0 к п – 1 делать        за j := я + 1 к п делать            если A [я] = A [j] тогда                вернуть ложь    вернуть истину

Без предварительной сортировки, в худшем случае, этот алгоритм потребовал бы, чтобы каждый элемент сравнивался с каждым другим элементом с двумя возможными результатами: либо в массиве нет повторяющихся элементов, либо последние два элемента в массиве являются дубликатами. Это приводит к O (п²) эффективность.

Теперь сравните это с аналогичным алгоритмом, который использует предварительную сортировку. Этот алгоритм сортирует введенный массив, а затем проверяет каждую пару элементов на наличие дубликата. Псевдокод представлен ниже:

алгоритм presortUniqueElementSearch (A [0 ...п]) является    sort (A [0 ...п])    за я := 0 к п – 1 делать        если A [я] = A [я + 1] тогда            вернуть ложь    вернуть истину

Как указывалось ранее, наименее эффективной частью этого алгоритма является сортировка массива, которая, если выбрана эффективная сортировка, будет выполняться за O (п бревно п). Но после сортировки массива его нужно пройти только один раз, что будет выполняться за O (п). Это приводит к O (п бревно п) эффективность.

Этот простой пример демонстрирует возможности такой техники улучшения ввода, как предварительная сортировка. Алгоритм пошел от квадратичный время выполнения линейный время выполнения, что приведет к ускорению для больших вводов.

На деревьях

Создание структур данных для более эффективного поиска в данных также является формой улучшения ввода. Помещение данных в дерево для хранения и поиска по входам - еще один популярный метод. Деревья используются в информатике и во многих разных типах деревьев - деревья двоичного поиска, Деревья АВЛ, красно-черные деревья, и 2-3 дерева и это лишь некоторые из них - были разработаны для правильного хранения, доступа и управления данными при сохранении их структуры. Деревья - это основная структура данных для реализации словаря.

Выгоды от помещения данных в дерево огромны, особенно если данные обрабатываются или повторно просматриваются. Деревья двоичного поиска - самый простой, но самый распространенный тип дерева для этой реализации. Вставка, удаление и поиск элементов в дереве - все это наихудший случай O (п), но чаще всего выполняются за O (log п). Это делает повторный поиск элементов еще быстрее для больших входных данных. Существует множество различных типов двоичных деревьев поиска, которые работают более эффективно и даже самобалансируются при добавлении и удалении элементов, например дерево AVL, которое имеет наихудший случай O (log п) для поиска, вставки и удаления.

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

Соответствие строк

Соответствие строк это сложный вопрос в мире программирование теперь это поисковые системы являются авангардом Интернета и онлайн-мира. Когда задано ключевое слово или строка, которую нужно искать среди миллионов и миллионов слов, потребуется невероятное количество времени, чтобы сопоставить этот строковый символ для каждого символа. Улучшение ввода позволяет изменять ввод, чтобы сделать этот процесс намного быстрее.

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

Этот алгоритм крайне неэффективен. Максимальное количество проверочных испытаний будет м-п+1 испытания, что делает эффективность большого O в худшем случае O (млн). В среднем случае максимальное количество проверочных испытаний никогда не будет достигнуто, и будут выполнены лишь несколько, что приведет к средней эффективности времени O (м+п).

Из-за необходимости более эффективных алгоритмов сопоставления строк было разработано несколько более быстрых алгоритмов, в большинстве из которых используется идея улучшения ввода. Ключ предварительно обрабатывается для сбора информации о том, что искать в тексте, и эта информация сохраняется, чтобы при необходимости обращаться к ним. Доступ к этой информации является постоянным по времени и значительно увеличивает эффективность работы алгоритмов, которые ее используют, в первую очередь Knuth-Morris-Pratt алгоритм и Бойер-Мур алгоритм. Эти алгоритмы, по большей части, используют одни и те же методы для достижения своей эффективности, главное отличие заключается в том, как составлен ключ.

Алгоритм Хорспула

В качестве демонстрации улучшения ввода при сопоставлении строк следует изучить упрощенную версию алгоритма Бойера-Мура, Хорспул алгоритм. Алгоритм начинается с пй символ текста м и сравнивает персонажа. Назовем этого персонажа Икс. Есть 4 возможных случая того, что может случиться дальше.

Случай 1: Первый возможный случай, когда персонаж Икс не в ключе. Если это произойдет, весь ключ может быть сдвинут на длину ключа.

Случай 2: Второй возможный случай: персонаж Икс не текущий персонаж, но Икс в ключе. В этом случае ключ сдвигается, чтобы выровнять крайнее правое вхождение символа. Икс.

Случай 3: Третий возможный случай - персонаж Икс совпадает с последним символом в ключе, но другие символы не полностью соответствуют ключу и Икс больше не встречается в ключе. Если это произойдет, весь ключ может быть сдвинут на длину ключа.

Случай 4: Четвертый и последний возможный случай - этот символ Икс соответствует ключу, но другие символы не полностью соответствуют ключу и Икс действительно повторяется в ключе. В этом случае ключ сдвигается, чтобы выровнять крайнее правое вхождение, если символ Икс.

Может показаться, что он не более эффективен, чем алгоритм перебора, поскольку он должен проверять все символы при каждой проверке. Однако, это не так. Алгоритм Хорспула использует таблицу сдвига для хранения количества символов, которые алгоритм должен сдвинуть, если он встречается с определенным символом. Входные данные предварительно вычисляются в таблице со всеми возможными символами, которые могут встретиться в тексте. Размер сдвига вычисляется с двумя вариантами: во-первых, если символ находится не в ключе, тогда размер сдвига равен п, длина ключа; или два, если символ появляется в ключе, то его значение сдвига - это расстояние от крайнего правого вхождения символа в первом п-1 символ в ключе. Алгоритму генератора таблицы сдвигов дается ключ и алфавит возможных символов, которые могут появиться в строке (K [0 ...п-1]) в качестве входных данных и возвращает таблицу сдвига (T [0 ...s-1]). Псевдокод для генератора таблицы сдвига и пример таблицы сдвига для строки «POTATO» показан ниже:

алгоритм shiftTableGenerator (K [0 ...п-1]) является    за я = 0 к s – 1 делать        Т [я] := м            за j := 0 к п – 2 делать                Т [P [j]] := п – 1 – j    возвращаться Т

Стол смены для 'POTATO'
персонаж Икс	А	B	C	...	О	п	...	Т	...	Z	_
значение сдвига	2	6	6	6	4	5	6	1	6	6	6

После того, как таблица сдвига построена на этапе улучшения входных данных, алгоритм выстраивает ключ и начинает выполнение. Алгоритм выполняется до совпадения подстрока текста м найден или ключ перекрывает последние символы текста м. Если алгоритм обнаруживает пару символов, которые не совпадают, он обращается к таблице для значения сдвига символа и соответственно смещается. Алгоритм Хорспула принимает ключ (K [0 ...п-1]) и текст (M [0 ...м-1]) и выводит либо индекс соответствующей подстроки, либо строку «Ключ не найден» в зависимости от результата. Псевдокод алгоритма Хорспула представлен ниже:

алгоритм HorspoolsAlgorithm (K [0 ...п-1]), M [0 ...м-1]) является    shiftTableGenerator (K [0 ...п-1])    я := п – 1    пока я ≤ м – 1 делать        k := 0        пока k ≤ м - 1 и К [п – 1 – k] = M [я – k] делать            k := k + 1            если k = м тогда                возвращаться я – п + 1            еще                я = я + T [M [я]]    возвращаться «Ключ не найден»

Хотя это может быть неочевидно, в худшем случае эффективность выполнения этого алгоритма составляет O (млн). К счастью, для случайных текстов эффективность выполнения линейна, O (н / м). Это помещает алгоритм Хорспула, который использует усовершенствование ввода, в гораздо более быстрый класс, чем алгоритм грубой силы для этой проблемы.

Связанные понятия

Расширение ввода часто используется как синоним предварительный расчет и предварительная обработка. Хотя они связаны между собой, необходимо отметить несколько важных различий.

Иногда предварительные вычисления и улучшения ввода могут использоваться как синонимы. Более конкретно, предварительное вычисление - это вычисление заданного входа до того, как что-либо еще будет сделано с входом. Часто создается таблица, которую можно просмотреть во время фактического выполнения алгоритма. Расширение ввода, которое вычисляет значения и присваивает их элементам ввода, можно классифицировать как предварительное вычисление, но на этом сходство заканчивается. Есть разделы улучшения ввода, которые не используют предварительные вычисления, и эти термины не должны использоваться совместно.
Говоря об изменении входных данных, часто неправильно используют предварительную обработку. В информатике препроцессор и препроцессор совершенно разные. Когда предварительная обработка используется в контексте, обычное намерение состоит в том, чтобы изобразить концепцию улучшения ввода, а не использование препроцессора. Реализация препроцессора - это концепция, в которой программа принимает входные данные и преобразует их в выходные данные, которые будут полностью использоваться другой программой. Это звучит как улучшение ввода, но применение препроцессора применяется к общей программе, которая обрабатывает исходный ввод, который должен быть выведен в формате, который компилятор может прочитать и затем скомпилировать.