Zadanie 4: Algorytm Nilsimsa - nilsims (3 pkt)
Zaimplementuj algorytm Nilsimsa do wykrywania podobnych tekstów:
class NilsimsHash:
"""Klasa implementująca algorytm Nilsimsa."""
def __init__(self):
"""Inicjalizuje hash Nilsimsa."""
pass
def _rolling_hash(self, text: str) -> list[int]:
"""
Oblicza rolling hash dla tekstu.
Args:
text: Tekst do przetworzenia
Returns:
Lista wartości rolling hash
"""
pass
def _trigrams(self, text: str) -> list[str]:
"""
Generuje trigramy z tekstu.
Args:
text: Tekst do przetworzenia
Returns:
Lista trigramów
"""
pass
def compute_hash(self, text: str) -> bytes:
"""
Oblicza hash Nilsimsa dla tekstu.
Args:
text: Tekst do zahashowania
Returns:
256-bitowy hash jako bytes
"""
pass
def compare_hashes(self, hash1: bytes, hash2: bytes) -> float:
"""
Porównuje dwa hashe Nilsimsa i zwraca stopień podobieństwa.
Args:
hash1: Pierwszy hash
hash2: Drugi hash
Returns:
Stopień podobieństwa w zakresie [0, 1]
"""
pass
def nilsims_similarity(text1: str, text2: str) -> float:
"""
Oblicza podobieństwo między dwoma tekstami używając algorytmu Nilsimsa.
Args:
text1: Pierwszy tekst
text2: Drugi tekst
Returns:
Stopień podobieństwa w zakresie [0, 1]
"""
pass
def find_similar_texts(target: str, candidates: list[str], threshold: float = 0.7) -> list[tuple[int, float]]:
"""
Znajduje teksty podobne do tekstu docelowego.
Args:
target: Tekst docelowy
candidates: Lista kandydatów
threshold: Próg podobieństwa
Returns:
Lista krotek (indeks, podobieństwo) dla tekstów powyżej progu
"""
passTwoje zadanie:
- Zaimplementuj klasę NilsimsHash z metodami do obliczania hash
- Zaimplementuj generowanie trigramów i rolling hash
- Zaimplementuj porównywanie hashów i obliczanie podobieństwa
- Zaimplementuj funkcje pomocnicze do znajdowania podobnych tekstów
- Przetestuj algorytm na różnych typach tekstów
Przykład:
text1 = "To jest przykładowy tekst do testowania"
text2 = "To jest przykładowy tekst dla testów"
similarity = nilsimsa_similarity(text1, text2) # powinno zwrócić wartość bliską 0.8-0.9Last updated on