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ą.

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.3 Prywatne
               6.4.3.1 CreateException
          6.4.4 Chronione
               6.4.4.2 GetUsedChar
               6.4.4.3 SetUsedChar
               6.4.4.4 SetOutputFileName
          6.4.5 Publiczne
               6.4.5.5 SetUsedChars
               6.4.5.6 SetLengths
               6.4.5.7 CombinationsCount
               6.4.5.8 GenerateWords
                    6.4.5.8.1 _BuildWord
                    6.4.5.8.2 _NextValidMarker
                    6.4.5.8.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:

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

Właściwości

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:

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:

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:

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:

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:

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:

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:

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:

_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:

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