Методы исправления ошибок. Рассмотрим два метода исправления ошибок: - исправление изолированного термина (isolated-term correction); - исправление с учетом контекста (context-sensitive correction). При исправлении изолированного термина термины запроса исправляются по отдельности. Пример со словом carot иллюстрирует этот подход. Этот метод не позволяет, например, обнаружить, что запрос flew form Heathrow содержит искаженный термин from, поскольку каждый из терминов запроса по отдельности записан правильно. Исправление опечаток Метод исправления изолированного термина реализуется двумя способами: - при помощи расстояния редактирования; - при помощи перекрытия k-грамм. Исправление опечаток Расстояние редактирования между двумя строками символов s1 и s2 — это минимальное количество операции редактирования (edit operations), с помощью которых строку s1 можно преобразовать в строку s2. Операции редактирования, позволяющие это сделать, включают в себя следующие преобразования: 2) удаление символа из строки 3) замена символа в строке другим символом. Исправление опечаток При указанном наборе операций редактирования расстояние редактирования называется расстоянием Левенштейна (Levenshtein distance). Например, расстояние редактирования между словами cat и dog равно трем. Исправление опечаток Для вычисления расстояния редактирования используется алгоритм динамического программирования. В качестве исходных данных термины s1 и s2 представлены в виде массивов. Во многих языках программирования этот алгоритм реализован в виде функции. Исправление опечаток Рассмотрим простой пример подсчета.
Do'stlaringiz bilan baham: |
