Efektywne Wyszukiwanie Anagramów

Zadanie

Dana jest lista wyrazów. Zadanie polega na efektywnym pogrupowaniu tak, że w każdej grupie znajdą się anagramy. Zakładamy, że wielkość liter nie ma znaczenia tj. A i a są tą samą literą. Wypisz następnie znalezione grupy. Przetestuj działania napisanego programu.

Analiza Zadania

Podczas rozwiązywania tego zadania należy rozwiązać dwie trudności. Pierwsza z nich dotyczy szybkości porównywania dwóch wyrazów czy są anagramami oraz szybkie grupowania wyrazów. Ten drugi problem może zostać rozwiązany poprzez zastosowanie słownika. Wtedy jest jednak potrzebny unikalny klucz, który będzie wspólny dla anagramów.

Klucz można utworzyć na podstawie wyrazu poprzez posortowanie jego liter. Nie jest to jednak metoda zbyt optymalna, ponieważ wymaga co najmniej O(n·log(n)) operacji. W anagramach kolejność liter nie ma znaczenia, więc przypiszmy każdemu znakowi alfabetu wartość tj. a = 1, b = 2, .., z = 26. Hash dla wyrazu będzie iloczynem podanych wartości dla liter w nim występujących. Przykładowo 'abc' będzie miało wartość 6. Tak samo jak 'acb' czy 'cba'.

Na podstawie obliczonego hasha algorytm będzie wstawiał odpowiednie dane do słownika. Na koniec wystarczy wypisać wartości przypisane do kolejnych kluczy jako oddzielne grupy.

Efektywność Algorytmu

Przyjmując, że na liście znajduje się n wyrazów, a wyszukanie pozycji do jego wstawienia wymaga log(n) porównań (wykorzystując wyszukiwanie binarne) to końcowa złożoność wynosi O(nlog(n)). Ograniczeniem może się okazać pojemność słownika - jeśli każdy wyraz będzie mieć inny hash to pomieszczenie wszystkich razem będzie niemożliwe.

Limity Implementacji

Jak długie wyrazy będzie można grupować? Otóż jeśli przyjmiemy, że długość wyrazu to k to będzie 26^k możliwych hashy. Dla takiej wartości potrzebna liczba bitów to: n ≥ log₂(26^k) = k·log₂26. Oto tabelka, która określa jak długie wyraz można umieścić w zależności od wybranego rozmiaru danych:

W powyższej tabeli zakładamy, że wyraz składa się z 26 liter alfabetu łacińskiego.

Implementacja

Hash

Funkcja Policz() ma za zadanie obliczyć hash dla podanego wyrazu.

1. def Policz(slowo):
2.   wynik = 1
3.   for znak in slowo:
4.     if (znak.isalpha()):
5.       wynik *= (ord(znak.lower()) - ord('a') + 1)
6.   return wynik

Funkcja składa się z pętli, która przechodzi po kolejnych znakach. Kiedy wykryje literę mnoży aktualny wynik przez jej pozycję w alfabecie. Znak jest zamieniany na mały znak, ponieważ znaki mogą mieć różną wielkość.

Hash

Funkcja Grupuj() na podstawie podanych wyrazów grupuje je w słowniku. Elementy są grupowane po obliczonym hashu funkcją Policz().

1. def Grupuj(wyrazy):
2.   slownik = {}
3.   for wyraz in wyrazy:
4.     hash = Policz(wyraz);
5.     if (not hash in slownik.keys()):
6.       lista = [wyraz]
7.       slownik[hash] = lista
8.     else:
9.       slownik[hash].append(wyraz)
10.   return slownik

Dla każdego wyrazu obliczany jest hash. Jeśli obliczona wartość nie występuje jako klucz to należy dopisać nowy. W przeciwnym wypadku wystarczy dopisać wyraz na koniec listy pod danym kluczem.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystać z poniższego kodu. Po zwróceniu wyniku program wypisuje znalezione grupy.

1. dane = ["bca", "abc", "dca", "dcb"]
2. wynik = Grupuj(dane)
4. grupa = 0
5. for hash, lista in wynik.items():
6.   print("Grupa ", grupa, end = ": ")
7.   for wyraz in lista:
8.     print(wyraz, end = " ")
9.   print()
10.   grupa += 1

• Kod źródłowy Implementacja