Programowanie w języku Delphi » Gotowce

Generator słów (metoda znaczników)

Wstęp


Temat opisuje klasę, która służy do generowania ciągów znaków wykorzystując wszystkie ich możliwe kombinacje. Możliwe jest ustalenie nazwy pliku, a także długości początkowej i końcowej generowanych słów. Algorytm napisany jest tak, by po ukończeniu budowania słów o danej długości, dodać jeden znak i rozpocząć nowe. W tym artykule postaram się dokładnie opisać każdy element klasy, by kod był jak najbardziej zrozumiały. Zachęcam wszystkich do zapoznania się z poniższą treścią.

Zaznaczam, że generator słowników jest wykorzystywany m.in. w atakach typu brute force, dlatego nie ponoszę odpowiedzialności za wykorzystanie klasy do celów przestępczych. Materiał jest prezentowany jedynie w celach edukacyjnych.


Spis treści

     1 Wstęp
     2 Brute force
     3 Metoda znaczników
     4 Dodatkowe moduły
     5 Typy danych
     6 Klasa TWordsGenerator
          6.1 Pola
          6.2 Właściwości
          6.3 Tworzenie i zwalnianie obiektu z pamięci
               6.3.1 Konstruktor
               6.3.2 Destruktor
          6.4 Metody
               6.4.1 Prywatne
                    6.4.1.1 CreateException
               6.4.2 Chronione
                    6.4.2.1 GetUsedChar
                    6.4.2.2 SetUsedChar
                    6.4.2.3 SetOutputFileName
               6.4.3 Publiczne
                    6.4.3.1 SetUsedChars
                    6.4.3.2 SetLengths
                    6.4.3.3 CombinationsCount
                    6.4.3.4 GenerateWords
                         6.4.3.4.1 _BuildWord
                         6.4.3.4.2 _NextValidMarker
                         6.4.3.4.3 Lista kroków (pseudojęzyk)
     7 Przykład użycia
     8 Ciekawostka
     9 Zakończenie
     10 Załączniki



Brute force


Brute force - jest to określenie tzw. algorytmu siłowego, którego zadaniem jest sprawdzenie wszystkich możliwych kombinacji w poszukiwaniu rozwiązania danego problemu. W slangu programistycznym, termin ten odnosi się do dowolnego algorytmu, który opiera sie na sukcesywnym sprawdzaniu wszystkich możliwych wariantów postępowania. Przykładem może być sprawdzenie wszystkich możliwych ścieżek między dwoma punktami, by wybrać jak najkrótszą.


Metoda znaczników


To sposób, dzięki któremu główna pętla algorytmu generującego słowa nie operuje bezpośrednio na macierzy zadanych znaków, lecz wykorzystuje drugą (o długości takiej, jaką ma mieć generowane słowo), w której zawarte są indeksy do nich. Operuje się na macierzy liczb, a słowo budowane jest na jej bazie. Próżno szukać opisu tej metody w sieci, gdyż opracowałem ją sam kilka lat temu. Sposób ten jest skuteczny przy czym łatwy do zaimplementowania. W dalszej części opiszę dokładniej na czym polega generowanie słów wykorzystując tą metodę.


Dodatkowe moduły


Klasa korzysta jedynie z modułu SysUtils, by można było tworzyć własne wyjątki. Żaden inny moduł nie jest wymagany.


Typy danych


Klasa korzysta z kilku własnoręcznie zdefiniowanych typów danych. Poniżej ich deklaracja:

type
  MarkerInt = -1 .. 255;
type
  TFileName = type String;
type
  TUsedCharsArr = array of Char;
type
  TMarkersArr = array of Byte;

Opis zadeklarowanych typów:

TypOpis
MarkerIntspecjalny typ całkowitoliczbowy do przeszukiwania macierzy znaczników
TFileNamealias standardowego typu String, stworzony jedynie dla właściwości przechowującej nazwę pliku
TUsedCharsArrdynamiczna macierz przechowująca wykorzystywane do generowania słów znaki
TMarkersArrdynamiczna macierz przechowująca znaczniki (czyli po prostu liczby - indeksy)

Jak łatwo zauważyć, maksymalna długość słowa może wynosić 255 znaków, choć nie sądzę, żeby ktoś potrzebował generować aż tak długie słowa (i miał tyle czasu). Jeżeli chodzi o typy danych to wszystko. Przejdźmy teraz do deklaracji klasy.


Klasa TWordsGenerator


Klasa ta zbudowana jest od podstaw, dziedzicząc jedynie właściwości i metody z bazowej klasy wszystkich obiektów - TObject.

Deklaracja klasy:

type
  TWordsGenerator = class(TObject)
  private
    FUsedCharsArr: TUsedCharsArr;
    FOutputFileName: TFileName;
    FBeginLength,
    FEndLength: Byte;
    procedure CreateException(ExcMessage: String);
  protected
    function GetUsedChar(Index: Integer): Char;
    procedure SetUsedChar(Index: Integer; UsedChar: Char);
    procedure SetOutputFileName(OutputFileName: TFileName);
  public
    constructor Create();
    destructor Destroy(); override;
  public
    procedure SetUsedChars(Chars: TUsedCharsArr); overload;
    procedure SetUsedChars(Chars: String); overload;
    procedure SetLengths(BeginLength, EndLength: Byte);
    procedure GenerateWords(); virtual;
    function CombinationsCount(): Extended;
  public
    property UsedChar[Index: Integer]: Char read GetUsedChar write SetUsedChar;
    property OutputFileName: TFileName read FOutputFileName write SetOutputFileName;
    property BeginLength: Byte read FBeginLength;
    property EndLength: Byte read FEndLength;
  end;

Klasa zawiera kilka ważnych pól, które służą do przechowywania podstawowych informacji. Metody służą do ich uzupełniania, a właściwości określają do nich dostęp. Poniżej szczegółowy opis poszczególnych elementów klasy.


Pola


IdentyfikatorOpis
FUsedCharsArrtypu TUsedCharsArr, dynamiczna macierz służąca do przechowywania wykorzystywanych do generowania słow znaków. Może przyjmować dowolne znaki kodu ASCII. Maksymalny rozmiar macierzy to 256 elementów, Próba wpisania większej ilości zakończy się wygenerowaniem wyjątku.
FOutputFileNametypu TFileName, łańcuch tekstowy przechowujący pełną nazwę pliku, do którego zostaną zapisane wszystkie wygenerowane słowa. Musi zawierać ścieżkę katalogu docelowego oraz nazwę pliku. Podczas zapisu informacji do tego pola, łańcuch zostaje sprawdzony pod kątem nieprawidłowych dla systemu MS Windows znaków. Jeżeli nazwa ta zawiera niedozwolony znak, zostanie wygenerowany odpowiedni wyjątek.
FBeginLengthtypu Byte, liczba określająca początkową długość słów. Musi być mniejsza lub równa końcowej długości.
FEndLengthtypu Byte, analogicznie do powyższej, określa końcową długość słów. Musi być większa lub równa początkowej długości. Obydwa te pola modyfikowane są poprzez jedną metodę.



Właściwości


IdentyfikatorOpis
UsedCharłączy z polem FUsedCharsArr, służy do modyfikacji (zarówno odczytu jak i zapisu) pojedynczego znaku w macierzy używanych znaków (jeżeli indeks jest niepoprawny, zostaje wygenerowany odpowiedni wyjątek)
OutputFileNamełączy z polem FOutputFileName, pozwala modyfikować nazwę pliku dla informacji wyjściowych, (podczas wpisywania nowej nazwy wykonywane jest sprawdzanie jej poprawności)
BeginLength, EndLengthłączy odpowiednio z polami FBeginLength oraz FEndLength, możliwy jest jedynie odczyt, gdyż zapis jest realizowany odpowiednią metodą (także sprawdzana jest ich poprawność)



Tworzenie i zwalnianie obiektu z pamięci


Do tworzenia i usuwania z pamięci obiektu klasy TWordsGenerator służą konstruktor i destruktor o standardowych nazwach. Poniżej ich szegółowy opis.


Konstruktor


Tworzenie obiektu realizowane jest za pomocą konstruktora o standardowej nazwie Create. Nie wymaga żadnych argumentów, stąd posiada prostą budowę. Jego definicja:

constructor TWordsGenerator.Create();
begin
  inherited Create();
 
  SetLength(FUsedCharsArr, 0);
  FOutputFileName := '';
  FBeginLength := 1;
  FEndLength := 1;
end;

Najpierw wywołany zostaje konstruktor klasy bazowej, po czym wszystkie prywatne pola klasy zostają uzupełnione domyślnymi wartościami. Stąd macierz wykorzystywanych znaków od tej pory posiada rozmiar 0, czyli jest pusta. Nazwa pliku także nie przyjmuje żadnej wartości (pusty łańcuch), a długość początkowa i końcowa ustawiona jest na 1. W późniejszym etapie korzystania z obiektu należy je odpowiednio uzupełnić odpowiednimi informacjami.


Destruktor


Definicja destruktora jest króciutka, zawiera jedynie wyzerowanie długości macierzy przechowującej znaki, oraz wywołania destruktora klasy rodzicielskiej:

destructor TWordsGenerator.Destroy();
begin
  SetLength(FUsedCharsArr, 0);
  inherited Destroy();
end;



Metody


Przedstawiając metody pozwolę sobie je podzielić na trzy grupy, odpowiednio dla poszczególnych stopni widoczności.


Prywatne


CreateException


W klasie istnieje jedna prywatna procedura CreateException, która służy do generowania wyjątku:

procedure TWordsGenerator.CreateException(ExcMessage: String);
begin
  raise Exception.Create(ExcMessage);
end;

Argumenty:

IdentyfikatorOpis
ExcMessage(ang. wiadomość wyjątku) - typu String, łańcuch znaków określający treść generowanego wyjątku (wszystkie własne wyjątki obsługiwane w metodach są w języku angielskim, by zachować jednorodność z językiem kompilatora)



Chronione


Metody chronione są wykorzystywane jedynie przez właściwości, do nadawania im nowych wartości, oraz do ich odczytywania. W żadnym innym miejscu nie są używane.


GetUsedChar


Metoda ta służy do odczytu pojedynczego znaku z macierzy. Definicja:

function TWordsGenerator.GetUsedChar(Index: Integer): Char;
begin
  if Index in [Low(FUsedCharsArr) .. High(FUsedCharsArr)] then
    Result := FUsedCharsArr[Index]
  else
    CreateException('Character index out of bounds');
end;

Argumenty:

IdentyfikatorOpis
Index(ang. indeks) - typu Integer, określa numer porządkowy znaku w macierzy. Jeżeli jest nieprawidłowy, zostaje wygenerowany wyjątek Character index out of bounds, co znaczy, że odwołaliśmy się do elementu w macierzy, który nie istnieje



SetUsedChar


Służy do modyfikacji pojedynczego znaku w macierzy. Definicja:

procedure TWordsGenerator.SetUsedChar(Index: Integer; UsedChar: Char);
begin
  if Index in [Low(FUsedCharsArr) .. High(FUsedCharsArr)] then
    FUsedCharsArr[Index] := UsedChar
  else
    CreateException('Character index out of bounds');
end;

Argumenty:

IdentyfikatorOpis
Index(ang. indeks) - typu Integer, analogicznie do powyższej metody, określa numer znaku w macierzy.
UsedChar(ang. używany znak) - typu Char, nowy znak, który zostaje zapisany w miejsce o indeksie Index.

Jeżeli indeks wprowadzanego znaku wykracza poza zakres macierzy, zostaje wygenerowany wyjątek Character index out of bounds;


SetOutputFileName


Służy do modyfikacji nazwy pliku dla danych wyjściowych. Definicja:

procedure TWordsGenerator.SetOutputFileName(OutputFileName: TFileName);
var
  sFileName: TFileName;
  I: Word;
begin
  if (Length(OutputFileName) = 0) or (Length(ExtractFileName(OutputFileName)) = 0) then
    CreateException('File name is incorrect')
  else
  begin
    sFileName := ExtractFileName(OutputFileName);
 
    for I := 1 to Length(sFileName) do
      if sFileName[I] in ['/', '\', ':', '*', '?', '"', '<', '>', '|'] then
      begin
        CreateException('File name contains incorrect characters');
        Exit;
      end;
 
    FOutputFileName := OutputFileName;
  end;
end;

Argumenty:

IdentyfikatorOpis
OutputFileName(ang. nazwa pliku wyjściowego) - typu TFileName, łańcuch znaków przechowujący nową nazwę pliku dla danych wyjściowych

W pierwszej kolejności sprawdzana jest długość nowej nazwy. Jeżeli argument jest pusty, zostaje wygenerowany wyjątek File name is incorrect. Jeśli łańcuch nie jest pusty, w następnym kroku do zmiennej sFileName zostaje zapisana jedynie wypakowana za sprawą funkcji ExtractFileName nazwa pliku, po czym w pętli zostaje sprawdzony każdy jej znak. Jeżeli nowa nazwa pliku zawiera niedozwolone w systemach z rodziny MS Windows znaki, zostaje wygenerowany wyjątek File name contains incorrect characters i procedura zostaje przerwana. Gdy sprawdzanie zawartości łańcucha zostanie ukończone, do pola FOutputFileName następuje przypisanie nowego łańcucha;

To wszystko jeśli chodzi o metody prywatne. W dalszej części opis metod publicznych (widocznych spoza modułu zawierającego kod klasy).


Publiczne


SetUsedChars


Dwie przeładowane metody, służą do wprowadzania znaków do macierzy. Przyjrzyjmy się ich deklaracji:

procedure SetUsedChars(Chars: TUsedCharsArr); overload;
procedure SetUsedChars(Chars: String); overload;

Mamy do dyspozycji wprowadzanie znaków z macierzy dynamicznej, lub łańcucha znaków.

Argumenty:

IdentyfikatorOpis
Chars(ang. znaki) - typu TUsedCharsArr, dynamiczna macierz przechowująca zbiór znaków, które będą wykorzystywane podczas generowania słów
Charstypu String, łańcuch znaków, który zostanie odpowiednio podzielony i przepisany do macierzy przechowującej znaki

Definicje metod:

procedure TWordsGenerator.SetUsedChars(Chars: TUsedCharsArr);
var
  I: Byte;
begin
  if Length(Chars) in [1 .. 255] then
  begin
    SetLength(FUsedCharsArr, Length(Chars));
 
    for I := 0 to High(Chars) do
      FUsedCharsArr[I] := Chars[I];
  end
  else
    CreateException('Number of characters is incorrect');
end;
 
procedure TWordsGenerator.SetUsedChars(Chars: String);
var
  I: Byte;
begin
  if Lentgh(Chars) in [1 .. 255] then
  begin
    SetLength(FUsedCharsArr, Length(Chars));
 
    for I := 0 to Length(Chars) - 1 do
      FUsedCharsArr[I] := Chars[I + 1];
  end
  else
    CreateException('Number of characters is incorrect');
end;

W obydwu metodach sprawdzana jest ilość wprowadzanych znaków. Jeśli jest ich zbyt wiele, lub nie ma ich w ogóle, zostaje wygenerowany wyjątek Number of characters is incorrect.


SetLengths


Służy do ustawienia długości początkowej i końcowej generowanych słów. Definicja:

procedure TWordsGenerator.SetLengths(BeginLength, EndLength: Byte);
begin
  if BeginLength <= EndLength then
  begin
    FBeginLength := BeginLength;
    FEndLength := EndLength;
  end
  else
    CreateException('Length values are incorrect');
end;

Argumenty:

IdentyfikatorOpis
BeginLength(ang. długość początkowa) - określa początkową długość generowanych słów
EndLength(ang. długość końcowa) - określa końcową długość, na niej zostaje zatrzymane generowanie słów, wartości długości przed wpisaniem są sprawdzane, by nie dopuścić do ich błędnego ustalenia (jeśli programista źle je poda, zostanie wygenerowany wyjątek Length values are incorrect, po czym program zostanie wstrzymany)



CombinationsCount


Metoda ta nie posiadająca żanych argumentów, służy do obliczenia ilości kombinacji dla zadanych znaków oraz długości początkowej i końcowej słów. Definicja:

function TWordsGenerator.CombinationsCount(): Extended;
 
  function _Power(iBase, iExponent: Integer): Extended;
  begin
    Result := Exp(Ln(iBase) * iExponent);
  end;
 
var
  I: Integer;
begin
  Result := 0;
 
  for I := FBeginLength to FEndLength do
    Result := Result + _Power(Length(FUsedCharsArr), I);
end;

Jak widać posiada wewnętrzną funkcję _Power, służącą do obliczania potęgi według zadanych parametrów:

IdentyfikatorOpis
iBase(ang. podstawa) - typu Integer, liczba, która będzie potęgowana
iExponent(ang. wykładnik) - także typu Integer, ilość potęgowań (stopień)

W pierwszej kolejności rezultat funkcji zostaje ustawiony na 0. Następnie jedyna pętla algorytmu potęguje ilość znaków macierzy FUsedCharsArr przez aktualną długość słowa, po czym wynik dodaje do rezultatu funkcji.


GenerateWords


Procedura nie posiada żadnych parametrów, uruchamia generowanie słów na podstawie zadanych kryteriów (zbioru znaków, długości słów oraz nazwy pliku dla danych wyjściowych). Pokrótce postaram się wytłumaczyć zasadę działania algorytmu oraz znaczenie jego elementów. Definicja:

procedure TWordsGenerator.GenerateWords();
 
  function _BuildWord(aMarkers: TMarkersArr): String;
  var
    I: Byte;
  begin
    Result := '';
 
    for I := 0 to High(aMarkers) do
      Result := Result + FUsedCharsArr[aMarkers[I]];
  end;
 
  function _NextValidMarker(aMarkers: TMarkersArr; const iMaxIndex: Byte): MarkerInt;
  var
    I: MarkerInt;
  begin
    Result := -1;
 
    for I := High(aMarkers) - 1 downto 0 do
      if aMarkers[I] < iMaxIndex then
      begin
        Result := I;
        Break;
      end;
  end;
 
var
  fOutput: TextFile;
  aMarkers: TMarkersArr;
  bLengthFinish: Boolean;
  iNextValidMarker: MarkerInt;
  iMaxIndex,
  I, J: Byte;
begin
  if (FOutputFileName <> '') and (Length(FUsedCharsArr) > 0) then
  begin
    AssignFile(fOutput, FOutputFileName);
    try
      ReWrite(fOutput);
      iMaxIndex := High(FUsedCharsArr);
 
      for I := 0 to FEndLength - FBeginLength do
      begin
        bLengthFinish := False;
        SetLength(aMarkers, FBeginLength + I);
 
        for J := 0 to High(aMarkers) do
          aMarkers[J] := 0;
 
        repeat
          WriteLn(fOutput, _BuildWord(aMarkers));
 
          if aMarkers[High(aMarkers)] + 1 > iMaxIndex then
          begin
            iNextValidMarker := _NextValidMarker(aMarkers, iMaxIndex);
            Flush(fOutput);
 
            if iNextValidMarker = -1 then
              bLengthFinish := True
            else
            begin
              Inc(aMarkers[iNextValidMarker]);
 
              for J := iNextValidMarker + 1 to High(aMarkers) do
                aMarkers[J] := 0;
            end;
          end
          else
            Inc(aMarkers[High(aMarkers)]);
        until bLengthFinish;
      end;
    finally
      Flush(fOutput);
      CloseFile(fOutput);
      SetLength(aMarkers, 0);
    end;
  end
  else
    CreateException('Class fields are not completed');
end;

Na początku zauważyć można, że wewnątrz metody zdefiniowane są dwie funkcje: _BuildWord oraz _NextValidMarker. Nie przejmujmy się nimi na razie, opiszę je w dalszej części.

Teraz przyszedł czas na wytłumaczenie czym tak naprawdę są i do czego służą tajemnicze znaczniki. Otóż wewnątrz klasy w polu FUsedCharsArr mamy zapisane znaki, jakich chcemy użyć do generowania słów. Tej macierzy jednak nie ruszamy, posłuży nam ona jedynie do odczytu zawartych w niej znaków. W bloku zmiennych mamy zadeklarowaną lokalną dynamiczną macierz aMarkers typu TMarkersArr. Jej rozmiar zostaje na początku ustawiony według długości początkowej słowa, po czym wypełnia się ją zerami. Dlaczego zerami? Dlatego, że wskazywać one będą na pierwszy element macierzy FUsedCharsArr, czyli na jej pierwszy znak. W każdej kolejnej iteracji pętli ostatni element macierzy znaczników zostaje w kółko podnoszony o 1, po czym odbywa się sprawdzanie, czy znacznik nie wykroczył poza zakres (maksymalna wartość znacznika przechowywana jest w zmiennej iMaxIndex). jeśli wykroczył - odbywa sie szukanie następnego, który jest mniejszy od maksimum. Znaleziony znacznik zostaje podniesiony o 1, a poprzednie zeruje się, by wskazywały znów na pierwszy znak. Inkrementowanie znaczników wykonuje się do czasu, aż nie znajdzie się następnego, który jest mniejszy od maksimum. Oznacza to, że zostały wykonane wszystkie kombinacje dla aktualnej długości słowa.

Na pierwszy rzut oka może się to wydawać skomplikowane, lecz opis lokalnych funkcji powinien to wyjaśnić.


_BuildWord

W ciele metody mamy zadeklarowane dwie funkcje. Pierwsza - _BuildWord - służy do zbudowania słowa w oparciu o macierz znaczników. Przyjrzyjmy się definicji:

function _BuildWord(aMarkers: TMarkersArr): String;
var
  I: Byte;
begin
  Result := '';
 
  for I := 0 to High(aMarkers) do
    Result := Result + FUsedCharsArr[aMarkers[I]];
end;

Argumenty:

IdentyfikatorOpis
aMarkers(ang. znaczniki) - typu TMarkersArr, macierz przechowująca aktualny stan znaczników

Jedynym argumentem jest macierz znaczników. Jak wcześniej wspomniałem, przechowuje znaczniki, czyli indeksy do poszczególnych używanych znaków. Rezultat funkcji zostaje ustawiony na pusty łańcuch, po czym rozpoczyna się przeszukiwanie macierzy znaczników. W każdej kolejnej iteracji pętli do rezultatu zostaje dodany znak z macierzy FUsedCharsArr o indeksie, który przechowuje macierz znaczników. Funkcja wywoływana jest każdorazowo po zmianie stanu znaczników, czyli ustaleniu nowego słowa.


_NextValidMarker

Drugą funkcją jest _NextValidMarker. Służy ona do znajdowania następnego ważnego znacznika w macierzy. "Ważnego" rozumie się pierwszego, który jest mniejszy od maksimum. Jeszcze raz rzućmy okiem na definicję funkcji:

function _NextValidMarker(aMarkers: TMarkersArr; const iMaxIndex: Byte): MarkerInt;
var
  I: MarkerInt;
begin
  Result := -1;
 
  for I := High(aMarkers) - 1 downto 0 do
    if aMarkers[I] < iMaxIndex then
    begin
      Result := I;
      Break;
    end;
end;

Argumenty:

IdentyfikatorOpis
aMarkers(ang. znaczniki) - typu TMarkersArr, macierz przechowująca aktualny stan znaczników
iMaxIndex(ang. maksymalna wartość indeksu) - typu Byte, indeks ostatniego znaku w macierzy FUsedCharsArr

W pierwszym kroku rezultat funkcji zostaje ustawiony na -1. Następnie w pętli zostaje realizowane wyszukiwanie kolejnego ważnego znacznika (wizualnie wyszukiwanie przebiega od prawej do lewej, z pominięciem ostatniego znacznika). Jeżeli zostanie znaleziony ważny znacznik, funkcja zwraca indeks znalezionego znacznika, po czym jej działanie zostaje przerwane. Jeśli żaden ważny znacznik nie zostanie znaleziony, rezultat funkcji pozostaje bez zmian.

Temat metody znaczników oraz lokalnych funkcji mamy opisany, wracamy więc do głównej metody GenerateWords. W pierwszej kolejności zostaje sprawdzone, czy pola są odpowiednio uzupełnione. Tyczy się to jedynie macierzy używanych znaków oraz nazwy pliku. Jeśli choćby jedna z nich nie została uzupełniona, zostaje wygenerowany wyjątek Class fields are not completed. Jeśli przyjmują jakieś wartości, następnie zostaje otwarty do zapisu plik o nazwie, jaką przechowuje pole FOutputFileName. Kolejnym krokiem jest ustawienie ilości iteracji pierwszej pętli, która wykona się tyle razy, ile jest różnicy między długością końcową a początkową + 1 (czyli przynajmniej jeden raz, jeśli długości są sobie równe). Następnie lokalna zmienna bLengthFinish zostaje ustawiona na False (zmienna ta służy do zatrzymywania pętli, która odpowiednio inkrementuje znaczniki, jeśli wszystkie kombinacje zostały sprawdzone, zmienna ta przyjmuje wartość True i pęla kończy działanie). Następnym krokiem jest ustawienie rozmiaru macierzy znaczników według aktualnej długości słowa (długość ta jest odczytywana z licznika głownej pętli), po czym zostaje wyzerowana. Teraz rozpoczyna się wewnętrzna pętla, która wykonuje się tyle razy, ile istnieje kombinacji z używanych znaków. W pierwszej kolejności zostaje zapisane słowo według aktualnego stanu znaczników (patrz: funkcja _BuildWord). Gdyby zapis słowa był w innym miejscu, słowo składające się jedynie z pierwszego używanego znaku zostałoby pominięte. Następnym krokiem jest sprawdzenie, czy ostatni znacznik można inkrementować, jeśli nie - wyszukiwany zostaje następny ważny. Gdy ważny znacznik zostanie znaleziony, zwiększa się jego wartość o 1, a poprzednie zeruje. Następnie należy opróżnić bufor zapisu procedurą Flush. Jeśli nie znaleziono następnego ważnego znacznika - wszystkie kombinacje zostały wygenerowane, dlatego zmienną bLengthFinish ustawia się na True, dzięki czemu wewnętrzna pętla kończy działanie. Cały mechanizm inkrementowania znaczników można przedstawić w prostej liście kroków.


Lista kroków (pseudojęzyk)

1. od 0 do Długość_końcowa - Długość_początkowa wykonuj
    1.1 ustaw bLengthFinish na False
    1.2 ustaw długość macierzy znaczników
    1.3 wyzeruj macierz znaczników
    1.4 powtarzaj
    |   1.4.1 zapisz słowo
    |   1.4.2 jeśli ostatni znacznik można inkrementować
    |   |   1.4.2.1 inkrementuj go
    |   jeśli nie
    |       1.4.2.2 znajdź następny ważny znacznik
    |       1.4.2.3 wyszyść bufor zapisu
    |       1.4.2.4 jeśli znaleziono
    |       |   1.4.2.4.1 inkrementuj znaleziony znacznik
    |       |   1.4.2.4.2 wyzeruj poprzednie znaczniki
    |       jeśli nie
    |           1.4.2.4.3 ustaw bLengthFinish na True
    aż zmienna bLengthFinish = True

Jeśli wewnętrzna pętla skończy działanie, wracamy do pętli, która ustalała ilość iteracji pętli według różnicy długości słow. I tak dalej, i tak dalej, aż wszystkie długości zostaną obsłużone. Po zakończeniu generowania słów plik zostaje zamknięty, a rozmiar macierzy znaczników zostaje wyzerowany. Tym samym procedura generowania słów zostaje zakończona.


Przykład użycia


Część opisowa ukończona, teraz czas na przykład. Poniżej kod prostego programu wraz z opisem instrukcji, który wykorzystuje obiekt z klasy TWordsGenerator:

program uWordsGenerator;
 
{$APPTYPE CONSOLE}
 
uses
  { Zawiera stałą SW_SHOWNORMAL }
  Windows,
  { Zawiera funkcję FloatToStr }
  SysUtils,
  { Zawiera funkcję ShellExecute }
  ShellAPI,
  { Zawiera klasę TWordsGenerator }
  uWrdGnrt in 'uWrdGnrt.pas';
 
var
  { deklaracja obiektu generatora }
  Generator: TWordsGenerator;
begin
  { utworzenie obiektu generatora }
  Generator := TWordsGenerator.Create();
 
  try
    with Generator do
    begin
      { nadanie nazwy plikowi dla danych wyjściowych }
      OutputFileName := 'C:\Words.txt';
      { ustalenie używanych znaków }
      SetUsedChars('AB');
      { ustalenie długości początkowej i końcowej słów }
      SetLengths(1, 4);
 
      { wyświetlenie liczby kombinacji }
      WriteLn('Liczba kombinacji: ', FloatToStr(CombinationsCount));
      { uruchomienie generatora słów }
      GenerateWords();
    end;
  finally
    { zwolnienie obiektu z pamięci }
    FreeAndNil(Generator);
    { otworzenie pliku z danymi wyjściowymi }
    ShellExecute(0, 'open', 'Words.txt', nil, 'C:\', SW_SHOWNORMAL);
    { oczekiwanie na wciśnięcie klawisza Enter }
    ReadLn;
  end;
end.

Uruchomienie programu spowoduje wygenerowanie wszystkich kombinacji słów (o długości od 1 do 4) z wykorzystaniem znaków A i B. Zawartość pliku C:\Words.txt będzie wyglądać następująco:

A
B
AA
AB
BA
BB
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB



Ciekawostka


Jeśli wykorzystywanymi znakami będą 0 i 1, wygenerowane słowa będą kolejnymi liczbami w systemie binarnym. Dla długości początkowej i końcowej równej 4, wynikiem będą wszystkie liczby z zakresu 0 .. F, czyli podstawowe liczby systemu szesnastkowego:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111



Zakończenie


To tyle, jeśli chodzi o generowanie słów metodą znaczników. Mam nadzieję, że artykuł wyczerpująco wyjaśnia każdy element klasy, i że kiedyś ktoś wykorzysta go w swoim programie. Jeżeli ma ktoś jakieś pytania bądź sugestie bardzo proszę o kontakt.

Dodatkowo zamieszczam plik uWrdGnrt.pas z kodem klasy. Projekt jest otwarty, więc można go dowolnie wykorzystywać w swoich programach.


Treść punktu 2 Brute force została napisana w oparciu o artukuł Atak brute force z Wikipedii.


Załączniki


uWrdGnrt.zip (1,95 KB)

3 komentarze

furious programming 2012-01-31 00:40

Dzięki @Adam :)

Dobrze, że napisałeś @Patryk27 o procedurze Flush() - faktycznie działa szybciej; Z tego co widzę, przemieściłeś Flush() spod WriteLn() za pobieranie nowego indeksu znacznika, oraz dopisałeś go w bloku finally - mam nadzieję, że to wszystko, co zmieniłeś w tym kodzie; Artykuł poprawiam, dziękuję za spostrzeżenie ;)

Patryk27 2012-01-30 19:03

Moduł i ogólnie artykuł fajny, aczkolwiek zmieniłbym to:

                  repeat
                    WriteLn(fOutput, _BuildWord(aMarkers));
                    Flush(fOutput);
 
                    case aMarkers[High(aMarkers)] + 1 > iMaxIndex of
                      True:  begin
                               iNextValidMarker := _NextValidMarker(aMarkers, iMaxIndex);
 
                               case iNextValidMarker of
                                 -1: bLengthFinish := True;
                               else
                                 Inc(aMarkers[iNextValidMarker]);
 
                                 for J := iNextValidMarker + 1 to High(aMarkers) do
                                   aMarkers[J] := 0;
                               end;
                             end;
 
                      False: Inc(aMarkers[High(aMarkers)]);
                    end;
                  until bLengthFinish;
                end;
            finally
              CloseFile(fOutput);SetLength(aMarkers, 0);
              SetLength(aMarkers, 0);
            end;

Na to:
                    repeat
                      WriteLn(fOutput, _BuildWord(aMarkers));

                      case aMarkers[High(aMarkers)] + 1 > iMaxIndex of
                        True:  begin
                                 iNextValidMarker := _NextValidMarker(aMarkers, iMaxIndex);
                                 Flush(fOutput);
                                 case iNextValidMarker of
                                   -1: bLengthFinish := True;
                                 else
                                   Inc(aMarkers[iNextValidMarker]);

                                   for J := iNextValidMarker + 1 to High(aMarkers) do
                                     aMarkers[J] := 0;
                                 end;
                               end;

                        False: Inc(aMarkers[High(aMarkers)]);
                      end;
                    until bLengthFinish;
                  end;
              finally
                Flush(fOutput);
                CloseFile(fOutput);
                SetLength(aMarkers, 0);
              end;

Przeprowadziłem testy i wyniki są takie:
Alfabet: abcdefghijklmnopqrstuvwxyz
SetLengths(1, 5)
stary kod - powyżej minuty (nie chciało mi się czekać więcej)
moja poprawka - 35 sekund

Adam Boduch 2012-01-30 10:30

Fajny artykul, dobre formatowanie kodu :)