Zwykłe porównywanie stringów czy to w php czy asp, sprowadza się do porównywania napisów znak po znaku i wyniku w postaci true lub false. Czasami jednak potrzebujemy porównać napisy powołując się nie na ich bezpośrednią równość, ale na ich podobieństwo.

Jednym z prostszych algorytmów, który pozwoli nam na zbadanie podobieństwa dwóch ciągów znaków jest algorytm Levenshteina, określający tzw. odległość Levenshteina.

Algorytm w oparciu o zdefiniowane wcześniej operacje proste (np. wstawienie znaku, usunięcie znaku, zmiana znaku na inny) określa najmniejszą liczbę operacji, potrzebnych do transformacji pierwszego napisu w drugi. Łatwo sobie wyobrazić, że dla identycznych napisów odległość Levenshteina będzie równa 0, natomiast dla dwóch całkowicie różnych napisów, będzie równa liczbie znaków dłuższego z ciągów. Krótko mówiąc im mniejsza odległość, tym napisy są bardziej do siebie podobne.

Algorytm ten można modyfikować dodając np. nowe operacje, lub przypisując operacjom wagi.

Warto zauważyć, że PHP dostarcza nam własną implementację algorytmu Levenshteina, możemy jej użyć wywołując funkcję levenshtein.

int levenshtein ( string $str1, string $str2 [, int $cost_ins, int $cost_rep, int $cost_del] )

Natomiast w C# porównywaniem string’ów musimy się zająć sami. Przykładowa implementacja może wyglądać na przykład tak:

public static int LevenshteinDistance(String s1, String s2)
{
	const int cost_ins = 1;
	const int cost_del = 1;
	const int cost_sub = 1;
 
	int n1 = s1.Length;
	int n2 = s2.Length;
 
	int[] p = new int[n2+1];
	int[] q = new int[n2+1];
	int[] r;
 
	p[0] = 0;
	for( int j = 1; j <= n2; ++j )
	{
		p[j] = p[j-1] + cost_ins;
	}
 
	for( int i = 1; i <= n1; ++i )
	{
		q[0] = p[0] + cost_del;
		for( int j = 1; j <= n2; ++j )
		{
			int d_del = p[j] + cost_del;
			int d_ins = q[j - 1] + cost_ins;
			int d_sub = p[j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : cost_sub);
			q[j] = Math.Min( Math.Min( d_del, d_ins ), d_sub );
		}
		r = p;
		p = q;
		q = r;
	}
	return p[n2];
}

Wynikiem funkcji Levenshteina jest liczba całkowita. Co jednak zrobić gdy na podstawie porównania ciągów znaków chcemy je klasyfikować? Liczba całkowita nie jest w tym wypadku zbyt wymowna. Lepszym pomysłem jest uzależnienie wyniku od maksymalnej długości ciągu.

Przykład:

public static float LevenshteinTextComparison(String s1, String s2)
{
	if (s1.Equals(String.Empty) && s2.Equals(String.Empty))
	{
		return 1;
	}
	return 1 - ((float)LevenshteinDistance(s1, s2) / (float)Math.Max(s1.Length, s2.Length));
}

Teraz zamiast mało mówiącej liczby całkowitej, otrzymujemy liczbę rzeczywistą z zakresu <0, 1> określającą podobieństwo napisów. Im bliżej jedynki tym ciągi są bardziej podobne i w drugą stronę, im bliżej zera, tym ciągi bardziej się od siebie różnią.

Przydatne linki:

http://pl.wikipedia.org/wiki/Odległość_Levenshteina
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance

Matt Cutts na swoim blogu zwrócił uwagę na uzależniające działanie Blogger Play. Szczerze mówiąc jest to moje pierwsze spotkanie z tym bardzo prostym i zarazem wciągającym serwisem.

Blogger Play to slideshow wyświetlający zdjęcia, które są aktualnie wrzucane do systemu Blogger przez ludzi na całym świecie.

Warto zauważyć, że Flickr również posiada podobną funkcjonalność.

Wyprodukowałem sobie dzisiaj bardzo prostą kontrolkę kompozytową. Jej zadaniem jest pokazywanie i chowanie div’a z tekstem. Całość odbywa się tylko po stronie klienta. Normalnie (mam na myśli HTML) byłoby to banalnie proste, niestety nie w ASP.

Div’a zastąpił mi Panel, a przycisk po wciśnięciu którego pojawia się panel, powstał jako oddzielna kontrolka (także kompozytowa). Wszystko ładnie złożyłem i opakowałem w metodę CreateChildControls(). Ku mojemu zdziwieniu JavaScript wywoływany po wciśnięciu przycisku powodował błąd. Okazuje się, że ClientId panelu jest puste (względnie nie zawiera wartości, której się spodziewam). Dlaczego? Otóż ClientId nie jest dostępne z poziomu metody CreateChildControls(), prawidłową wartość możemy uzyskać dopiero tuż przed wyrenderowaniem kontrolki, czyli np. na preRenderze.

protected override void OnPreRender(EventArgs e)
{
	// tutaj możemy się odwołać do ClientId kontrolek
}

Faktem jest, że unikalne ID tagów html’owych generowanych przez ASP może być zbudowane tylko przy kompletnym drzewie kontrolek, ale czy nie można było zaoszczędzić czasu i napisać o tym w dokumentacji właściwości ClientId?

Jestem świeżo po urlopie. Góry, śnieg i narty. Bez laptopa i internetu (no prawie ). Przede wszystkim bez codziennego pośpiechu. Chwila oddechu, która pozwoliła na oderwanie się od problemów, natłoku myśli i informacji. Mała szansa na zerwanie z codzienną rutyną i szarymi ulicami miasta.

Wracam, próbuję nadrobić zaległości, zaczynam czytać i na co trafiam?

- Wiesz, oprócz komputerów jest jeszcze rzeczywistość: kwiaty, drzewa, żywi ludzie…
- To znaczy gdzie, za firewallem?…

Rozbroiło mnie to totalnie