Laboratorium 7 - Wyszukiwanie przybliżone

Zdognie z nanjwoymszi baniadmai perzporawdzomyni na bytyrijskch uweniretasytch nie ma zenacznia kojnoleść ltier przy zpiasie dengao sołwa. Nwajżanszyeim jest, aby prieszwa i otatsnia lteria była na siwom mijsecu, ptzosałoe mgoą być w niaedziłe i w dszalym cąigu nie pwinono to sawrztać polbemórw ze zozumierniem tksetu. Dzijee się tak datgelo, ze nie czamyty wyszistkch lteir w sołwie, ale cłae sołwa od razu.

wyjątek z całości za Mattem Davisem z University of Cmabrigde.

Zakres materiału

Metody algorytmiczne. Operacje wejścia/wyjścia na plikach. Przetwarzanie tekstu.

Przygotowanie do zajęć

Przed przystąpieniem do zajęć przygotuj programy testowe realizujące następującą funkcjonalność (zadabaj, by przygotowane programy miały strukturę - podział na funkcje - odpowiednią do postawionego poniżej zadania):

• Program, który wczyta plik tekstowy, wyświetlając każde słowo w oddzielnej linii. Za słowo należy uznać ciąg kolejnych liter, wszelkie znaki nie będące literami należy pominąć. Do rozpoznania, czy wczytany znak jest literą należy użyć funkcji
  int isalpha(int c). Można przyjąć, że długość słowa jest ograniczona.

• Przetestuj działanie programu z różnymi ustawieniami lokalizacyjnymi.

• Program, który wczyta podaną na standardowym wejściu linię tekstu, zapyta użytkownika o numer słowa, a następnie wyświetli podaną linię podkreślając wybrane słowo znakami ^.

Ponadto również:

• Zapoznaj się z pojęciami odległości Hamminga i Levenshteina oraz ich modyfikacjami.

• Zaproponuj algorytm pozwalający na realizację następującego zadania:
  
  Napisać program, którego celem będzie przybliżone wyszukiwanie we wskazanym pliku zadanego wzorca. Program ma wypisywać na standardowym wyjściu numer linii w której wystąpił wzorzec wraz z samą linią z zaznaczonym miejscem stwierdzenia dopasowania. Dopasowanie zostaje stwierdzone jeśli:
  • ciąg znaków dokładnie odpowiada ciągowi znaków stanowiących wzorzec;
  • w ciągu znaków występuje „niedopasowanie'' do wzorca w liczbie nie większej niż dwa polegające na

    literówce

    - wystąpieniu w dopasowywanym ciągu innego znaku w stosunku do znaków wzorca;

    braku znaku

    - pominięciu w dopasowywanym ciągu znaku ze wzorca;

    znaku nadmiarowym

    - wystąpieniu w dopasowywanym ciągu dodatkowego znaku;

    czeskim błędzie

    - zamianie miejscami dwóch kolejnych znaków w dopasowywanym ciągu w stosunku do wzorca.

• Zaproponuj podział problemu na podproblemy. Określ specyfikację procedur/funkcji rozwiązujących wyszczególnione podproblemy.
• Zaproponuj struktury danych niezbędne do realizacji algorytmu.

Zadania do wykonania

• Napisać program implementujący zaproponowany algorytm. Nie zapomnieć o wprowadzaniu do pliku komentarzy równocześnie z wprowadzaniem do niego kodu programu. Program powinien wskazywać znalezione wystąpienia przez ich podkreślenie umieszczone w linii następnej po linii zawierającej przeszukiwany tekst, np. dla wyszukiwania słowa gait otrzymujemy

  29 he said. 'We shall have to wait for you to get  thin again.' 'How long
        ^^^^                    ^^^^                      ^^^^^
  

• Przetestować program dla różnych tekstów oraz przy wyszukiwaniu słów o różnej długości. Obserwacje uwzględnić we wnioskach.

Informacje dodatkowe

• W katalogu ~mucha/edu/info2/ksiazki/ na diablo dostępne są teksty książek w języku polskim i angielskim, które mogą zostać wykorzystane w testach programów.
• Bieżące ustawienia lokalizacyjne można sprawdzić poleceniem locale. Za klasyfikację znaków odpowiedzialna jest zmienna LC_CTYPE. Parametry występujące w opisie każdej ze zmiennej oznaczają, w kolejności: język, kraj oraz kodowanie znaków, przy czym język jest obowiązkowy, natomiast pozostałe dwa - opcjonalne. Na przykład:
  LC_CTYPE="pl_PL.ISO-8859-2"
  oznacza, że za litery uznawane znaki z alfabetu polskiego w kodowaniu wg normy ISO-8859-2 (nazywanej także Latin-2). Zmiany ustawień zmiennych można dokonać poleceniem systemowym export (w powłoce bash), przykładowo, by zmienić alfabet na niemiecki w odmianie występującej w Austrii w ośmiobitowym kodowaniu Unicode, należy wykonać polecenie
  export LC_CTYPE=de_AT.UTF-8
  (Uwaga: zamiast zmiany wartości pojedynczych zmiennych można także zmienić zmienną LANG, co spowoduje odpowiednie ustawienie wszystkich zmiennych LC_*).

• Zainteresowani mechanizmami internacjonalizacji w systemie Linux (zwanymi w skrócie i18n) mogą dowiedzieć się więcej z prezentacji Marcina Wolińskiego.

Sprawozdanie

Sprawozdanie powinno zawierać:

• Imię i nazwisko autora, temat ćwiczenia, datę wykonania;
• Kod źródłowy programu;
• Testy programu (opis przebiegu z wynikami) w tym kolejno:
  • Co dany test ma na celu;
  • Metoda testowania - dane wejściowe;
  • Dane wyjściowe zwrócone w teście przez program;
  • Rezultat testu - ocena plus ewentualny komentarz;
• Wnioski końcowe.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2008 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -html_version 3.2,latin2,unicode -split 0 -no_navigation PProg_lab_07.tex

The translation was initiated by Robert Muszynski on 2015-12-16