Szukaj!

Tym razem coś bardzo praktycznego. Zajmiemy się wyszukiwaniem tekstów. Rzecz prawie wprost do zastosowania w rozbudowanych cd-romowych prezentacjach. I prawie-prawie wprost w małych/średnich serwisach.

Założenia (znaczy ograniczenia):

  1. Szukamy początków słów.
  2. Szukamy co najmniej trzech pierwszych znaków.
  3. Wielkość liter nie istotna.
  4. Ignorujemy częstotliwość występowania słów.
  5. Indeksowana treść nie jest zbyt duża (do około miliona znaków).

Ograniczenia 2-5 narzuciłem ze względu na przejrzystość (hyhyhy) dywagacji. Ograniczenie 1 w tym modelu jest nie do obejścia – trzeba je realizować inaczej. Tylko po co...

Całość w Jscript i dla msxml2. Jeżeli ktoś chce się pokusić o przepisanie skryptów w innym narzeczu i potestować dla innego parsera – zapraszam do współpracy.

Skrypty uruchamiamy z linii komend poleceniem:

cscript <skrypt.js>

O co walczymy?

W odcinku walczymy o stworzenie indeksu pozwalającego na szybkie wyszukiwanie słów. Indeksem będą oczywiście pliki xml. Dlaczego pliki a nie plik? Gigantyczne xml’e obciążają niestety system. Można sobie na nie (czasami pozwolić) przy rzadko wykonywanych operacjach. Przy operacjach częstych zamulają skutecznie system. Przy przetwarzaniu dużej ilości danych często stajemy przed wyborem: mało dużych albo dużo małych plików. Rozsądnym kompromisem jest średnio średnich z tendencją do dużo małych :-)

Z mojej praktyki wynika, że granicą sensownego przetwarzania dla pojedynczego pliku xml jest 100 kB.

Nasz indeks będzie zbiorem plików o nazwach jak pierwsze trzy litery słów, w których trzymać będziemy informacje o dalszym ciągu słów. Stad właśnie ograniczenie, szukania do co najmniej trzech liter.

Parole, parole, parole...

Była taka piosenka dawno dawno temu. Rodzice pewnie będą ją znać. Chodzi o słowa, czyli co indeksować. Istnieją różne szkoły. Ja przez długi czas traktowałem teksty kilometrowym wyrażeniem regularnym, które co modyfikowałem po każdym wysypaniu się na dziwnych szlaczkach. I działa to nawet szybko, ale jest ciężkie w utrzymaniu.

Podejdźmy to tematu inaczej. Słowo jak wiadomo składa się z liter. Przyjmijmy, że literą będzie dla nas każdy znak dozwolony w nazwie xml’owego elementu. Utworzymy listę takich znaków dla UTF’a.

05/01.js

var txml=new ActiveXObject('msxml2.domdocument');
var xmlns='urn:szomiz:lista-znakow';

txml.appendChild(txml.createProcessingInstruction('xml','version="1.0" encoding="UTF-8"'));
tml=txml.appendChild(txml.createNode(1,'Znaki',xmlns));

for(var k=33;k<65535;k++){

Przelatujemy przez cały zakres UTF-8

znak=String.fromCharCode(k).toLowerCase(); try{ if(maly=duzy){

Jeżeli środowisko nie widzi różnicy między małym a dużym dodajemy mały:

tml.appendChild(txml.createNode(1,maly,xmlns)); }else{ if(duzy.toLowerCase()!=duzy){

Jeżeli zmniejszony duży wygląda inaczej niż mały – dopisujemy do listy:

tml.appendChild(txml.createNode(1,maly,xmlns)); }; }; }catch(e){

Tutaj nic – wszak szukamy znaków mogących być nazwą węzła :-)

} };

Ponieważ założyliśmy nierozróżnianie wielkości liter mamy do dyspozycji znaki, które mogą je zastąpić.

for(var k=0;k<10;k++){ tml.appendChild(txml.createNode(1,String.fromCharCode(k+71),xmlns)); };

Luźnych znaków jest więcej niż cyfr, więc możemy ewentualnie dodać do indeksowania inne potrzebne robaczki.

txml.save('znaki.xml');

Zapuszczamy z linii poleceń:

cscript 01.js

Można by się wgryźć w specyfikacje UTF’a i XML’a w celu ograniczenia zakresów. Ale my przecież nie o tym. Zwłaszcza, że plik wygenerował się w przyzwoitym tempie. Poza tym operacja jest jednorazowa – z wygenerowanego pliku można korzystać dowolną ilość razy.

Jego rozmiar będzie miał niestety wpływ na szybkość indeksowania. Warto się jednak pomęczyć – możliwość trzymania w indeksie japońskich robaczków i polskich literek jest kusząca a nie wpłynie na prędkość wyszukiwania. Przy pracy z konkretną stroną kodową można stworzyć plik z jej deklaracją i zakresem znaków.

Dziabanie

Wiemy już co w naszym tekście może być indeksowanymi literami. Wyrazy będą wszystkim co ograniczone jest znakami, których za litery nie uznaliśmy. Ich listę stworzymy oczywiście transformacją. Zanim jednak: zmodyfikujemy plik z danymi do indeksowania (zmiana wielkości liter):

05/02.js

var t1=(new Date()).getTime();
var txml=new ActiveXObject('msxml2.domdocument');
var txsl=new ActiveXObject('msxml2.domdocument');

Ładujemy xml’a z treścią do zaindeksowania:

txml.load('doc/00.xml');

Wybieramy wszystkie węzły tekstowe:

ttml=txml.selectNodes('//text()'); for(var k=0; k<ttml.length;k++){

Zamieniamy ich treść na małe litery:

ttml(k).nodeValue=ttml(k).nodeValue.toLowerCase(); }; txsl.load('wyrazy02.xsl');

Transformujemy cały plik:

txml.transformNodeToObject(txsl,txml); WScript.Echo((new Date()).getTime()-t1) txml.save('res/02-00.xml');

Zamianę znaków można by zrealizować xsl’em – ale wtedy byłby on nieco zakręcony, no i plik wygenerowany w poprzednim przykładzie musiałby wyglądać nieco inaczej. A całość szybsza by pewnie i tak nie była.

05/wyrazy02.xsl

Wczytujemy do zmiennej plik z wygenerowaną lista znaków:

<xsl:param name="znaki" select="document('znaki.xml')/*"/> <xsl:template match="/*"> <Wyrazy>

Wybieramy do przetworzenia wszystkie węzły typu text:

<xsl:apply-templates select="//text()"/> </Wyrazy> </xsl:template>

Szablon dla węzłów typu text (mała rekurencja):

<xsl:template match="text()">

Parametr z tekstem do przetworzenia (dla pierwszego wywołania wartość domyślna: zawartość bieżącego węzła) Przy okazji zamieniamy cyfry na odpowiadające im wielkie litery. Jeżeli postanowiśmy indeksować inne robaczki – właśnie tutaj trzeba to uwzględnić:

<xsl:param name="text" select="translate(.,'0123456789','GHIJKLMNOP')"/>

Parametr z długością tekstu do przetworzenia w następnym wywołaniu (dla pierwszego wywołania: wartość domyślna: długość tekstu bieżącego węzła - 1):

<xsl:param name="length" select="string-length($text) - 1"/>

Parametr z listą znaków uznanych wcześniej za godne indeksowania (dla pierwszego wywołania brak wartości domyślnej:

<xsl:param name="name"/>

Zmienna z pierwszym znakiem przekazanego tekstu ($text):

<xsl:variable name="char" select="substring($text,1,1)"/> <xsl:choose>

Jeżeli na wygenerowanej liście znaków znajduje się pierwszy z analizowanego stringa...

<xsl:when test="$znaki/*[name()=$char]">

... wykonujemy szablon jeszcze raz...

<xsl:apply-templates select=".">

... ścinając tekst do przetworzenia o jedną pozycję,

<xsl:with-param name="text" select="substring($text,2,$length)"/>

zmniejszajmy parametr informujący o długości tekstu do przetworzenia (można liczyć za każdym razem, ale to będzie szybsze),

<xsl:with-param name="length" select="$length - 1"/>

Na koniec do ciągu zdetekowanych dotychczas koszernych znaków dodajemy bieżący

<xsl:with-param name="name" select="concat($name,$char)"/> </xsl:apply-templates> </xsl:when>

Jeżeli jednak bieżącego znaku nie ma na wygenerowanej liście to natknęliśmy się na koniec słowa:

<xsl:otherwise> <xsl:if test="string-length($name)>2">

Dla ciągów dłuższych niż dwa znaki tworzymy węzeł zjawiska uznawanego za wyraz:

<xsl:element name="{$name}"/> </xsl:if>

I jeżeli jest jeszcze co przetwarzać...

<xsl:if test="$text!=''"> <xsl:apply-templates select=".">

... przetwarzamy modyfikując jak wcześniej dwa pierwsze parametry:

<xsl:with-param name="text" select="substring($text,2,$length)"/> <xsl:with-param name="length" select="$length - 1"/>

Parametru name nie wysyłamy, bo zgromadzone przez niego znaki zostały przed chwilą wykorzystane (jeżeli było ich więcej niż trzy).

</xsl:apply-templates> </xsl:if> </xsl:otherwise> </xsl:choose> </xsl:template>

Zapuszczamy z linii poleceń:

cscript 02.js

Po czym udajemy się siku albo na szybkiego papierosa – na słabszych maszynach może to chwilę potrwać (skrypt zwróci czas swojego wykonania).

xsl:key

Wynik (lista słów spełniająca założone przez nas kryteria) zapisał się w katalogu res/. Całość niestety chwilę trwała. Jak na mój gust stanowczo za długo. Zakombinujemy trochę, ze skryptem, tak by do transformacji przekazać jeden plik. O korzystaniu z document() na jakiś czas zapominamy.

05/03.js

var t1=(new Date()).getTime();
var sxml=new ActiveXObject('msxml2.domdocument');
var txml=new ActiveXObject('msxml2.domdocument');
var txsl=new ActiveXObject('msxml2.domdocument');

Wczytujemy wygenerowaną listę znaków, z których mogą składać się wyrazy:

sxml.load('znaki.xml'); sml=sxml.documentElement;

Wczytujemy plik z tekstami do zaindeksowania:

txml.load('doc/00.xml'); ttml=txml.selectNodes('//text()');

Wybieramy z niego wszystkie węzły tekstowe:

for(var k=0;k<ttml.length;k++){

I wklejamy je do xml’a z listą dopuszczalnych znaków:

sml.appendChild(sxml.createTextNode(ttml(k).nodeValue.toLowerCase()+' ')); }; //sxml.save('res/03-00a.xml');

Transformujemy z wykorzystaniem xsl:key:

txsl.load('wyrazy03.xsl'); sxml.transformNodeToObject(txsl,txml); WScript.Echo((new Date()).getTime()-t1) txml.save('res/03-00.xml');

Nieznacznie zmieniamy transformację

05/wyrazy03.xsl

Definiujemy klucz (nazwa – dowolna, match – węzły brane pod uwagę w kluczu, use – wartość klucza):

<xsl:key name="chars" match="/*/*" use="name()"/>

W tym szablonie nic się nie zmienia

<xsl:template match="/*"><Wyrazy><xsl:apply-templates... <xsl:template match="text()">

Parametry i zmienne bez zmian:

<xsl:param name="text" select="translate(.,'0123456789','GHIJKLMNOP')"/> <xsl:... <xsl:choose>

Za to istotna zmiana w warunku. Jeżeli w zdefiniowanym kluczu występuje wartość jak w drugim argumencie key():

<xsl:when test="key('chars',$char)">

Dalej bez zmian:

<xsl:apply-templates select="."><xsl:with-param... </xsl:when> <xsl:otherwise><xsl:if test="string-length($name)>2">... </xsl:choose> </xsl:template> </xsl:stylesheet>

Uruchamiamy:

cscript 03.js

Lepiej? U mnie 02.js wykonuje się około 20 sekund natomiast 03.js około 0.3 sekundy. A pliki wyjściowe wyglądają tak samo (kto nie wierzy może sprawdzić).

Żeby życie było tak proste jak przykłady z MSDN’a...

Wszystko pięknie – niestety przy zbyt dużych dawkach tekstów procesor zgłasza błąd przepełnienia. Można to sprawdzić przetwarzając w poprzednim przykładzie doc/04.xml zamiast doc/00.xml.

Musimy się przed tym jakoś zabezpieczyć. Sprawdzimy najpierw, czy transformacja może się przytkać i jeżeli tak – podzielimy obrabiany tekst na kilka kawałków. String o długości 3600 transformacji (przy msxml2) nie przytyka. I takimi kawałkami będziemy tekst przerabiać (można się pobawić i znaleźć optymalną dla wydajności wartość – to może być nawet ciekawe).

05/04.js

Tworzymy zrąb dokumentu do przechowywania wyników:

rxml.appendChild(rxml.createProcessingInstruction('xml','version="1.0" encoding="UTF-8"')); rml=rxml.appendChild(rxml.createNode(1,'Group','urn:szomiz:wyrazy-z-tekstu'));

Dalej jak poprzednio:

sxml.load('znaki.xml'); sml=sxml.documentElement; txsl.load('wyrazy04.xsl'); txml.load('doc/00.xml'); tml=txml.documentElement; ttml=txml.selectNodes('//text()'); var res='',pos; for(var k=0;k<ttml.length;k++){

Z zawartości wszystkich węzłów tekstowych tworzymy jedna zmienna: res+=ttml(k).nodeValue.toLowerCase()+' ';

};

Którą ścinamy do skutku i przetwarzamy:

while(res.length){

Szukamy pierwszej spacji po 3600-tnym znaku:

pos=res.indexOf(' ',3600); if(pos!=-1){

Jeżeli znaleziona – wysyłamy do przetworzenia odpowiedni kawałek tekstu:

ssml=sml.appendChild(sxml.createTextNode(res.substr(0,pos))); res=res.substr(pos+1); }else{

Jeżeli nie – wysyłamy resztę:

ssml=sml.appendChild(sxml.createTextNode(res)); res='';

A jak ktoś dzieli częściej enterem niż spacją, to niech poszuka dowcipu Wibrator i beret :-P

}

Każdy kawałek transformujemy w znany sposób:

sxml.transformNodeToObject(txsl,txml);

Wynik przetworzenia każdego kolejnego kawałka dopinamy do rxml:

rml.appendChild(txml.documentElement.cloneNode(1));

Usuwamy węzeł tekstowy wysłany do przetworzenia:

sml.removeChild(ssml); }; //rxml.save('res/04-00A.xml'); txsl.load('drzewo04.xsl'); rxml.transformNodeToObject(txsl,rxml); WScript.Echo((new Date()).getTime()-t1); rxml.save('res/04-00.xml');

Transformacja wyłapującą wyrazy bez zmian. Dodamy transformację, która pogrupuje wyrazy po trzech pierwszych znakach i usunie powtórzenia:

05/drzewo04.xsl

Dla przypomnienia: ze względu na dzielenie indeksowanego tekstu słowa znajdują się na trzecim poziomie xml’a:

<xsl:key name="words" match="/wrd:*/wrd:*/wrd:*" use="name()"/>

W wartości klucza można kombinować (ale żeby nie było zbyt słodko nie można kombinować w odwołaniu do jego wartości):

<xsl:key name="roots" match="/wrd:*/wrd:*/wrd:*" use="substring(name(),1,3)"/> <xsl:template match="/wrd:*"> <Drzewo>

Ignorujemy węzły stworzone przez cloneNode(1) – i niech nikt nie wpadnie na pomysł, żeby w skrypcie przepinać węzły po sztuce!

<xsl:apply-templates select="*/*"/> </Drzewo> </xsl:template> <xsl:template match="wrd:*/wrd:*">

Dla każdego dopasowanego powyżej węzła ustalamy trzy pierwsze znaki nazwy:

<xsl:variable name="root" select="substring(name(),1,3)"/>

Sprawdzamy, czy (automatycznie wygenerowany) id bieżącego węzła to ten sam id, co pierwszego węzła w kluczu z początkowymi znakami wyrazów:

<xsl:if test="generate-id()=generate-id(key('roots',$root)[1])">

I jeżeli tak – tworzymy węzeł o nazwie jak trzy pierwsze znaki:

<xsl:element name="{$root}">

A następnie wysyłamy do wykonania (z oddzielnym mode) wszystkie węzły z klucza zaczynające się tak jak bieżący:

<xsl:apply-templates select="key('roots',$root)" mode="ciach"/> </xsl:element> </xsl:if> </xsl:template> <xsl:template match="wrd:*/wrd:*" mode="ciach">

Sprawdzamy, czy bieżące słowo nie jest trzyliterowe:

<xsl:if test="string-length(name())>3">

A jeżeli nie jest, sprawdzamy, czy id bieżącego węzła jest takie same jak id pierwszego węzła w kluczu nazw:

<xsl:if test="generate-id()=generate-id(key('words',name())[1])"> <xsl:element name="{substring(name(),4,string-length(name()) - 3)}"/>

Powyższy warunek w celu wyeliminowania duplikatów.

</xsl:if> </xsl:if> </xsl:template>

Linia poleceń:

cscript 04.js

I podziwiamy wynik (katalog res/).

Zasadniczo można by było skończyć – wrzucić w węzły identyfikator dokumentu, przelecieć przez wszystkie dokumenty posklejać wyniki dla poszczególnych pierwszych trzech wystąpień liter i w tym szukać.

Nawet by to zadziałało, ale pliki było by dość duże i trzeba by je przeszukiwać przy pomocy wyrażeń typu //*[starts-with(name(),$cos)], co na prędkość wyszukiwania zbyt dobrze by nie wpłynęło. Dlatego:

Przekształcamy dalej

Rozbijmy wnętrze trzyliterowych węzłów na poszczególne znaki. W jednym rzucie pewnie by się dało, ale transformacja była by monstrualna. Dlatego będziemy przekształcać dokument dopóki będą w nim występować węzły: /*//*/*[not(*) and string-length(name())>1]

Wyrażenie takie a nie inne, bo na drugim poziomie aktualnego dokumentu mają prawo wystąpić trzyliterowe elementy bez elementów podrzędnych (się, ale, itp.).

05/05.js

Do skryptu dopisujemy kilka linijek:

txsl.load('drzewo05.xsl'); while(txml.selectSingleNode('/*//*/*[string-length(name())>1]')){

Znaczy, dopóki w dokumencie wystąpi na co najmniej trzecim poziomie węzeł z nazwą dłuższą niż jeden znak – walczymy.

txml.transformNodeToObject(txsl,txml); };

05/drzewo05.xsl

Wiemy, że w wartości klucza można kombinować, zakombinujemy więc jeszcze bardziej. Do pierwszego nazwy elementu i jej pierwszego znaku dodamy id węzła nadrzędnego:

<xsl:key name="wrd" match="//tre:*[not(*)]" use="concat(name(),',',generate-id(..))"/> <xsl:key name="chr" match="//tre:*[not(*)]" use="concat(substring(name(),1,1),',',generate-id(..))"/>

Dla węzłów: głównego, na drugim poziomie, oraz posiadających dzieci – kopiujemy wyprodukowaną (wcześniej) strukturę:

<xsl:template match="/tre:* | tre:*[*] | /tre:*/tre:*"> <xsl:copy> <xsl:apply-templates/> </xsl:copy> </xsl:template>

Dla pozostałych przeprowadzamy operację grupowania po pierwszym znaku i wydzielenia:

<xsl:template match="tre:*/tre:*/tre:*[not(*)]">

Jeżeli id bieżącego jest taki sam jak id pierwszego z klucza, takiego że, pierwsza litera nazwy oraz id nadrzędnego wygląda tak samo jak wartość z klucza:

<xsl:if test="generate-id()=generate-id(key('chr',concat(substring(name(),1,1),',',generate-id(..)))[1])">

Tworzymy węzeł o nazwie jak pierwszy znak namierzonego...

<xsl:element name="{substring(name(),1,1)}">

... oraz wysyłamy do przetworzenia wszystkie węzły z klucza których nazwy zaczynają się jak bieżący, a węzeł nadrzędny jest ten sam co aktualnego:

<xsl:apply-templates select="key('chr',concat(substring(name(),1,1),',',generate-id(..)))" mode="ciach"/> </xsl:element> </xsl:if> </xsl:template> <xsl:template match="tre:*" mode="ciach"> <xsl:if test="string-length(name())>1"> <xsl:element name="{substring(name(),2,string-length(name())-1)}"/> </xsl:if> </xsl:template>

Uruchamiamy:

cscript 05.js

Wyrazy ślicznie podziabane, możemy utworzyć:

Indeks właściwy

Jeżeli ktoś jeszcze nie zauważył to indeksujemy Pana Tadeusza. W pliku doc/00.xml jest spis ksiąg. Atrybuty id wskazują na plik, w którym siedzi zawartość konkretnej księgi. Niewiele się to różni od zawartości strony internetowej, na której zamiast id mamy href...

05/06.js

Informacje o indeksie przechowywać będziemy w jednym pliku. Poza „spisem treści” indeksu (można trzymać tam mapowania id’ów na url’e) umieścimy w nim informację o literach oraz trzyliterowych początkach słów wykorzystywanych w indeksie.

ixml.appendChild(ixml.createProcessingInstruction('xml','version="1.0" encoding="UTF-8"')); iml=ixml.appendChild(ixml.createNode(1,'Index','urn:szomiz:indeks-tekstowy'));

Element do trzymania informacji o literach trzyliterowych znalezionych w indeksowanym tekście:

iml.appendChild(ixml.createNode(1,'Chars','urn:szomiz:indeks-tekstowy'));

Element do trzymania informacji o wykorzystywanych trzyliterowych początkach stwierdzonych wyrazów:

iml.appendChild(ixml.createNode(1,'Roots','urn:szomiz:indeks-tekstowy'));

Element pierwszego dokumentu do indeksowania:

with(iml.appendChild(ixml.createNode(1,'Item','urn:szomiz:indeks-tekstowy'))){

I jego identyfikator:

setAttribute('id','00'); }; while(iiml=ixml.selectSingleNode('//idx:Item[string(@time)!="'+tNow+'"]')){

Utworzony przed chwilą element będzie pierwszym spełniającym powyższy warunek, wysyłamy go funkcji (która – między innymi – utworzy elementy informujące o następnych dokumentach do zaindeksowania):

oneIndex(iiml); ... }; function oneIndex(nod){

Odczytujemy id dokumentu do zaindeksowania:

var pid=nod.getAttribute('id');

Ustawiamy w przekazanym węźle informację o czasie rozpoczęcia procesu indeksowania:

nod.setAttribute('time',tNow);

Ładujemy dokument do zaindeksowania:

txml.load('doc/'+pid+'.xml');

Znajdujemy w nim wszystkie atrybuty wskazujące na dokumenty zalinkowane z bieżącym:

ttml=txml.selectNodes('//@id'); for(var k=0;k<ttml.length;k++){

Do (globalnego) ixml dopisujemy węzły z informacją o znalezionych dokumentach:

iml.appendChild(ixml.createNode(1,'Item','urn:szomiz:indeks-tekstowy')).setAttribute('id',ttml(k).nodeValue); };

Definiujemy lokalny xmldom do pośrednich transformacji:

var rxml=new ActiveXObject('msxml2.domdocument'); rxml.appendChild(rxml.createProcessingInstruction('xml','version="1.0" encoding="UTF-8"')); rml=rxml.appendChild(rxml.createNode(1,'Group','urn:szomiz:wyrazy-z-tekstu'));

I dalej jak w poprzednim przykładzie z poprawką na to, że ostatnia transformacja wykonywana jest do txml zadeklarowanego globalnie.

... txml.save(sts/'+pid+'.xml') };

Powyższa funkcja zostawia w txml drzewko wyrazów z pierwszego niezaindeksowanego pliku. Za utworzenie właściwych indeksów odpowiedzialna jest transformacja z drugiej części while:

while(iiml=ixml.selectSingleNode('//idx:Item[string(@time)!="'+tNow+'"]')){ oneIndex(iiml);

Do (aktualnego) pliku indeksu dopinamy ostanie wygenerowane drzewko (globalny txml):

iiml.appendChild(txml.documentElement.cloneNode(1));

Przetwarzamy transformacją znajdującą (między innymi) różnice pomiędzy ewentualnie istniejącym na dysku (informacja w /*/idx:Roots) a wygenerowanym ostatnio drzewkiem:

ixml.transformNodeToObject(ixsl,ixml);

Wybieramy węzły z połączonymi informacjami:

iiml=ixml.selectNodes('//idx:Item/*'); for(var k=0;k<iiml.length;k++){

I zapisujemy je na dysku pod właściwymi nazwami:

txml.replaceChild(iiml(k).cloneNode(1),txml.documentElement); txml.save('sts/'+iiml(k).getAttribute('file')+'.xml') }; iiml.removeAll(); };

Czary dzieją się w (zakręconej) transformacji:

05/indeks.xsl

I proponuję jej analizę przenieść na dzień następny, bo robi całkiem inne rzeczy niż te wcześniejsze :-/.

Transformacja wykonywana jest dwa razy (drugi raz na wyniku pierwszego razu).

Klucz dla istniejących początków zaindeksowanych słów (przy każdym przejściu przez js’owe while będzie się powiększał):

<xsl:key name="roots" match="/*/idx:Roots/*" use="name()"/>

Klucz dla istniejących zaindeksowanych znaków (uwaga jak wyżej):

<xsl:key name="chars" match="/*/idx:Chars/*" use="name()"/>

Przepisujemy zawartość głównego elementu:

<xsl:template match="/idx:*"> <xsl:copy> <xsl:copy-of select="@*"/> <xsl:apply-templates select="idx:*"/> </xsl:copy> </xsl:template>

Innych (w głównym!) też przepisujemy:

<xsl:template match="idx:*"> <xsl:copy> <xsl:copy-of select="@*"/> <xsl:apply-templates/> </xsl:copy> </xsl:template>

Dotychczasowa zawartość listy początków słów zasadniczo bez zmian:

<xsl:template match="idx:Roots"> <xsl:copy> <xsl:copy-of select="*"/>

Ale sprawdzamy czy nie pojawiła się jakaś nowa trzyliterówka:

<xsl:apply-templates select="//idx:*/tre:Drzewo/tre:*" mode="roots"/> </xsl:copy> </xsl:template> <xsl:template match="idx:*/tre:Drzewo/tre:*" mode="roots"> <xsl:if test="not(key('roots',name()))">

No właśnie – jak nie ma: dopisujemy:

<xsl:element name="{name()}"/> </xsl:if> </xsl:template>

Lista wystąpioych znaków (ltier) zasadniczo tak samo:

<xsl:template match="idx:Chars"> <xsl:copy> <xsl:copy-of select="*"/> <xsl:apply-templates select="//tre:Drzewo//tre:*" mode="chars"/> </xsl:copy> </xsl:template>

Ale dopisujemy je po sztuce z trzyliterowych początków:

<xsl:template match="tre:Drzewo/tre:*" mode="chars"> <xsl:if test="not(key('chars',substring(name(),1,1)))"> <xsl:element name="{substring(name(),1,1)}"/> </xsl:if> <xsl:if test="not(key('chars',substring(name(),2,1)))"> <xsl:element name="{substring(name(),2,1)}"/> </xsl:if> <xsl:if test="not(key('chars',substring(name(),3,1)))"> <xsl:element name="{substring(name(),3,1)}"/> </xsl:if> </xsl:template> <xsl:template match="tre:Drzewo/tre:*//tre:*" mode="chars"> <xsl:if test="not(key('chars',name()))"> <xsl:element name="{name()}"/> </xsl:if> </xsl:template>

I stad to co ważne/nowe w tej transformacji:

<xsl:template match="idx:*/tre:*">

Przelatujemy przez dopięty węzeł ostatniego drzewka:

<xsl:apply-templates/> </xsl:template> <xsl:template match="tre:Drzewo/tre:*">

Ustalamy nazwę pliku do zapisania (operacja odwrotna do przeprowadzonej na początku indeksowania):

<xsl:variable name="file" select="translate(name(),'GHIJKLMNOP','0123456789')"/> <xsl:element name="{name()}">

Przepisujemy węzeł trzyliterowego początku wyrazu:

<xsl:attribute name="file"><xsl:value-of select="$file"/></xsl:attribute> <xsl:choose> <xsl:when test="key('roots',name())">

Jeżeli bieżąca trzyliterówka nie wystąpiła we wcześniejszych plikach:

<xsl:apply-templates select="*" mode="newIdx"/>

Wysyłamy ją do szablonu tworzącego nowe drzewko w gałęzi wyjściowej:

<xsl:if test="not(*)"> <xsl:value-of select="ancestor::idx:Item/@id"/> <xsl:text>,</xsl:text> </xsl:if> </xsl:when> <xsl:otherwise>

Jeżeli wystąpiła, wysyłamy do przetworzenia aktualny (zapisywany po każdym przejściu) plik trzyliterówki znajdujący się na dysku (z bieżącym – wygenerowanym przed chwilą – węzłem jako parametrem):

<xsl:apply-templates select="document(concat('sts/',$file,'.xml'))/*" mode="oldNew"> <xsl:with-param name="new" select="."/> </xsl:apply-templates> </xsl:otherwise> </xsl:choose> </xsl:element> </xsl:template>

Dla (gałęzi) drzewek nie występujących w aktualnej wersji indeksu:

<xsl:template match="tre:*" mode="newIdx">

Tworzymy węzeł o nazwie jak bieżący (xsl:copy – NIE, jesteśmy w innej przestrzeni nazw):

<xsl:element name="{name()}"> <xsl:if test="not(*)">

Jeżeli przekazane drzewko nie ma elementów podrzędnych odnotowujemy wystąpienie słowa:

<xsl:value-of select="ancestor::idx:Item/@id"/> <xsl:text>,</xsl:text>

(tak na prawdę wszystkich form słowa z bieżącego dokumentu, zawierających się w najdłuższym).

</xsl:if> <xsl:apply-templates select="*" mode="newIdx"/> </xsl:element> </xsl:template>

Jeżeli w dotychczasowym indeksie istnieje plik dla bieżącej trzyliterówki:

<xsl:template match="idx:*" mode="oldNew"> <xsl:param name="new"/> <xsl:variable name="old" select="."/>

Przepisujemy identyfikatory zaindeksowanych wcześniej stron:

<xsl:copy-of select="text()"/> <xsl:if test="not($new/*)">

Dla wystąpienia wyrazu dodajemy tekst z aktualnym identyfikatorem zasobu:

<xsl:value-of select="$new/ancestor::*[@id]/@id"/> <xsl:text>,</xsl:text> </xsl:if>

Uwaga: w tym szablonie name($new)=name($old)! Przepraszamy się z xsl:for-each (dało by się to apply, ale było by kompletnie nieczytelne \-:

<xsl:for-each select="*">

Dla każdego węzła w istniejącym indeksie:

<xsl:choose> <xsl:when test="not($new/*[name()=name(current())])">

Kopiujemy zawartość, jeżeli w nie ma w nim gałęzi o nazwie takiej jak przekazane drzewko:

<xsl:copy-of select="."/> </xsl:when> <xsl:otherwise>

Jeżeli jest – tworzymy węzeł o nazwie jak bieżący:

<xsl:copy>

I wysyłamy do przetworzenia bieżący (czyli podrzędny względem kontekstu szablonu – jesteśmy w xsl:for-each):

<xsl:apply-templates select="." mode="oldNew">

Z odpowiednim parametrem nowego węzła:

<xsl:with-param name="new" select="$new/*[name()=name(current())]"/> </xsl:apply-templates> </xsl:copy> </xsl:otherwise> </xsl:choose> </xsl:for-each>

Może się jednak zdarzyć, że wygenerowane drzewko...

<xsl:for-each select="$new/*">

... zawiera węzeł niewystępujący w starym indeksie:

<xsl:if test="not($old/*[name()=name(current())])">

Wtedy przepisujemy nowe drzewko znanąj już metodą:

<xsl:apply-templates select="." mode="newIdx"/> </xsl:if> </xsl:for-each> </xsl:template>

Odpalamy:

cscript 06.js

Po czym udajemy się na normalnego papierosa, albo szybkie piwo (zaindeksowanie całego Pana Tadeusza chwilę potrwa).

Po co ten cyrk?

Ano po to, żeby szybko wyszukiwać. Na dobrą sprawę w przypadku małych (i średnich) serwisów można sobie indeksowanie zapuścić w domu, z Łindołsa i wrzucać na serwer gotowe pliki (w tym różnicowo). Na dobrą sprawę samo indeksowanie można przeprowadzać różnicowo – potrzebny jest kawałek js’a i transformacji, który będzie usuwał z plików wskazania na te zasoby, które się od ostatniego indeksowania zmieniły. Tutaj polecam skorzystanie z MD5 treści zasobu (w MS do osiągnięcia przy pomocy biblioteki capicom) przechowywanego w index.xml, jako atrybut, obok daty indeksowania. Na prawdę można poszaleć :-)

05/07.js

Króciutki skrypt pozwalający na korzystanie z indeksu:

var ixml=new ActiveXObject('msxml2.domdocument'); var ixsl=new ActiveXObject('msxml2.domdocument'); if(!WScript.Arguments.length){ WScript.Echo('Podaj poczatki szukanych wyrazow!'); WScript.Quit(); }; ixml.load('sts/index.xml'); ixsl.load('search.xsl'); ixml.documentElement.setAttribute('q',WScript.Arguments(0)); ixml.transformNodeToObject(ixsl,ixml); //ixml.save('res/07-query.xml'); ixml.transformNodeToObject(ixsl,ixml); WScript.Echo(ixml.xml); //ixml.save('res/07-request.xml'); WScript.Echo((new Date()).getTime()-t1);

Jak widać – naprawdę krótki. Przepisanie go na dowolny język to 5 minut roboty – to co istotne dzieje się w dwukrotnym wykonaniu transformacji. Też krótkiej :-)

05/search.xsl

<xsl:key name="roots" match="/*/idx:Roots/*" use="name()"/>
<xsl:key name="chars" match="/*/idx:Chars/*" use="name()"/>
<xsl:template match="/idx:*">
  <Query>
    <xsl:copy-of select="@q"/>
    <xsl:apply-templates select="@q"/>
    <xsl:copy-of select="idx:Roots"/>
  </Query>
</xsl:template>
<xsl:template match="@q">
  <xsl:param name="text" select="translate(.,'0123456789','GHIJKLMNOP')"/><xsl:...
  <xsl:choose><xsl:when test="key('chars',$char)"><xsl:apply-templates...
</xsl:template>
<xsl:template match="/res:*">
  <Reqest>
    <xsl:copy-of select="@q"/>
    <xsl:apply-templates select="res:*"/>
  </Reqest>
</xsl:template>
<xsl:template match="res:*">
  <xsl:variable name="root" select="substring(name(),1,3)"/>
  <Result for="{name()}">
    <xsl:if test="key('roots',$root)">
      <xsl:apply-templates select="document(concat('sts/',$root,'.xml'))/*" mode="search">
        <xsl:with-param name="path" select="substring-after(name(),$root)"/>
      </xsl:apply-templates>
    </xsl:if>
  </Result>
</xsl:template>
<xsl:template match="idx:*" mode="search">
  <xsl:param name="path"/>
  <xsl:variable name="char" select="substring($path,1,1)"/>
  <xsl:choose>
    <xsl:when test="string($path)=''"><xsl:apply-templates/></xsl:when>
    <xsl:otherwise>
      <xsl:apply-templates select="*[name()=$char]" mode="search">
        <xsl:with-param name="path" select="substring-after($path,$char)"/>
      </xsl:apply-templates>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Bez komentarzy do kodu, go jak ktoś zrozumiał poprzedni przykład, to bieżący sam byłby w stanie (i to lepiej) wymyślić.

I tyle:

cscript 07.js "Natenczas Wojski wyjął"

:-)

Wyciąganie wniosków z tego, które wyrazy wystąpiły we wszystkich, a które w niektórych zostawiam Uczestnikom.

Całość można oczywiście popełnić z zachowaniem informacji o częstotliwości występowania, z opcją wyszukiwania całych wyrazów, itp. Ale my tutaj do myślenia zmuszamy, a nie dajemy gotowce. Jeżeli ktoś gotowca potrzebuje – może negocjować.

Jeżeli ktoś zastosuje powyższe do własnych celów z modyfikacjami mającymi na celu osiągnięcie konkretnych efektów – chętnie zamieszczę. Onet jest tak miły, że zdjął limit z konta.

Oczywiście namolnie i upierdliwie przypominam o zasadach licencjonowania – ten jeden procent na szczytny cel naprawdę nic nie kosztuje!

Jak znajdę chwilę czasu to napiszę "produkcyjną" indeksiarko-wyszukiwarkę ją w serwisie podepnę. Tak, tak, wyszukiwanie bez server-side:-)

UWAGA: To jest robocza wersja dokumentu i jego załączników. Udostępniona zasadniczo w celu testowania oraz zgłaszania uwag i spostrzeżeń.

Zasady korzystania:

  1. Do celów edukacyjnych, niezwiązanych z wykonywaną pracą zawodową (na przykład uczniowie, studenci i innihobbyści nie zarabiający pieniędzy szeroko rozumianą działalnością informatyczną) – na własne potrzebybezpłatnie i bez ograniczeń, ale w przypadku osiągania dochodów prośba o rozważenie skorzystania zasad zawartych w punkcie 2a.
  2. Do celów edukacyjnych związanych bezpośrednio z wykonywaną pracą/sposobem osiągania przychodów (na przykładprogramiści i koderzy) – na własne potrzeby (w tym wykonywania pracy zawodowej/osiągania przychodów) bez ograniczeń po spełnieniu następujących wymagań:
    1. Wsparcie kwotą jaką korzystający uzna za słuszną:
      Fundacja SERCE – Europejskie Centrum Przyjaźni Dziecięcej
      Organizacja Pożytku Publicznego
      58-100 Świdnica, ul. Kościelna 15
      numer konta: 42 1020 5138 0000 9102 0067 8961
      tytuł wpłaty: darowiznana rzecz organizacji pożytku publicznego
      Będzie mi miło jeżeli dostanę na maila (skompresowany:-) skan/zrzut z ekranu z informacją o wpłacie.
    2. W przypadku bezpośredniego korzystania z udostępnionego kodu (w tym zmodyfikowanego, bez ingerencji w istotę rozwiązań) proszę o zamieszczenie w kodzie informacji o kursie z jego adresem: http://szomiz.republika.pl/.
    3. Przy wysyłaniu do przeglądarki wyników działania kodu wykonanego na serwerze zamieszczenie informacji o korzystaniu z kursu w tagu META.
    4. Poinformowanie mnie (jeżeli nie zabraniają tego zobowiązania wobec osób trzecich) o projektach i rozwiązaniach w których kod udostępniony w kursie został wykorzystany.
  3. Do wszelkich innych celów, zwłaszcza związanych z wykonywaną/prowadzoną działalnością edukacyjna, szkoleniową, wydawniczą lub publikacyjną – wykorzystanie możliwe wyłącznie po indywidualnym określeniu zasad i warunków pomiędzy autorem kursu a korzystającym.
  4. Osoby, wnoszące swój wkład w treści zawarte w kursie udzielają autorowi kursu nieodpłatnej licencji umożliwiającej co wykorzystanie i udostępnienie na określonych tutaj zasadach.
  5. Oczywiście nie biorę żadnej odpowiedzialności za rezultaty działania kodu i jego modyfikacji :-)
© Sławomir Zimosz - wszelkie prawa zastrzeżone.
Przedruk, publikacja części lub całości bez wiedzy i zgody autora zabronione.
Kontakt: szomiz@poczta.onet.pl