Попрактикуватись в задачах, що вирішуються методом динамічного програмування; реалізувати просту програму виправлення помилок у написанні слів
Ми всі звикли, що фактично будь-яке текстове поле для вводу, чи то цілий текстовий документ в редакторі, чи просто створення нового посту в інстаграмі супроводжується перевіркою граматики - неправильні слова підкреслюються та надаються рекомендації по виправленню.
В цій роботі ми створимо просту систему, що буде здатна знаходити та виправляти помилки у написанні слів. Завдання буде складатися з двох частин: проста, підготовча частина, за яку можна отримати бали тільки в першій тиждень (перші два практичних заняття), та основна частина.
- Прочитайте 9 розділ підручника Grokking Algorithms, щоб освіжити знання про динамічне програмування, особливо частину про знаходження найбільшого спільного підрядка та послідовності.
- Скачайте підготовлений список англійських слів. Це один з так званих SCOWL - Spell Checker Oriented Word Lists, тобто спеціально підготовлених списків слів саме для використання в якості бази для перевірки написання.
- Напишіть просту консольну програму, що зчитує у користувача довільне речення (все до натискання клавіші
Enter). Розбийте речення на слова, виключіть пунктуаційні знаки, та перевірте кожне слово на входження у список. Для кожного слова, яке ви не знайшли, виведіть підказку на екран. Наприклад:
> Togay a have the greatest tahk!
< Looks like you have typos in next words: 'Togay', 'tahk'Тепер ми готові не просто підсвітити слова, яких немає в словнику, а спробувати знайти підказки для виправлення. Почнемо з простого:
- Реалізуйте розглянутий на лекції алгоритм Longest common subsequence. Пам'ятайте - код копіпастити не можна! Прочитайте алгоритм, розберіть його ще раз та реалізуйте самостійно. Для кожного "невідомого" слова знайдіть 5 найкращих кандидатів та виводіть їх користувачу. Спробуйте підібрати приклади, коли використання цього алгоритму призведе до некоректних підказок.
- Гарним способом знайти можливі варіанти виправлення є пошук edit distance двох рядків. За визначенням, це кількість модифікуючих операцій які необхідно зробити над одним рядком, щоб отримати інший.
Підвидом, який ми будемо використовувати, є відстань Левенштейна, яка враховує операції вставки, заміни або видалення символів. Наприклад, відстань Левенштейна між рядками crate та flat - 3:crate -> frate (заміна c на f), frate -> frat (видалення e), frat -> flat (заміна r на l). Для знаходження відстані Левенштейна зазвичай використовується динамічне програмування.
Детальне пояснення концепції відстані Левенштейна та сам алгоритм можна прочитати тут. Модифікуйте програму, так щоб виводити підказки використовуючи алгоритм Левенштейна.
Існує певна модифікації алгоритму, що дозволяє враховувати окрім наведених операцій (вставка, заміна, видалення), ще й перестановку місцями літер. Це дуже корисно для виправлення помилок, оскільки часто випадково виходить написати щось типу "Приівт!" замість "Привіт!". Для того щоб отримати повний бал за цю роботу знайдіть цю модифікацію та реалізуйте.
- В чому суть методики динамічного програмування? Наведіть приклади відомих вам алгоритмів
- Які переваги має динамічне програмування перед рекурсією?
- Що таке відстань Левенштейна та як її порахувати?
Максимальний бал - 8:
- Підготовча частина - 1 бал;
- Реалізація алгоритму Левенштейна - 2 бали;
- Реалізація алгоритму, що враховує перестановки - 1 бал;
- Теоретичні питання - 2 бали;
- Виконання додаткового практичного завдання при здачі - 2 бали;