Posts mit dem Label fuzzy werden angezeigt. Alle Posts anzeigen
Posts mit dem Label fuzzy werden angezeigt. Alle Posts anzeigen

Mittwoch, 6. Juni 2012

Name Matching (NDATA) mit einem Thesaurus "erweitern"

Zum Thema Oracle TEXT Name Matching hatten wir ja bereits einige Blog Postings. Heute möchte ich das Thema nochmal aufgreifen und besonders die Erweiterbarkeit mit einem Thesaurus vorstellen. Zunächst zur Ausgangssituation: Wir legen eine Tabelle an und füllen diese mit ein paar Namen:
create table tab_namen (
  id           number(10),
  vorname      varchar2(100),
  nachname     varchar2(100)
)
/

insert into tab_namen values (1, 'Carsten','Czarski');
insert into tab_namen values (2, 'Ulrike', 'Schwinn');
insert into tab_namen values (3, 'Max',    'Meier');
insert into tab_namen values (4, 'Moritz', 'Meyer');
insert into tab_namen values (5, 'Franz',  'Mayer');
insert into tab_namen values (6, 'Fritz',  'Maier');
Damit man einen Oracle TEXT Index anlegen kann, der auch alle Namen enthält, muss man nun mit einem Multicolumn-Datastore oder einem User-Datastore arbeiten. Da ich die Namen aber gerne per NDATA (Name Matching) und per "klassischer" Fuzzy-Suche (FUZZY-Operator) finden möchte, brauche ich einen User-Datastore (Blog-Posting). Also zuerst die PL/SQL-Prozedur anlegen ...
 create or replace procedure namen_uds_proc(
  rid  in            rowid,
  tlob in out nocopy varchar2
) is
  l_vorname  tab_namen.vorname%type;
  l_nachname tab_namen.nachname%type;
begin
  select vorname, nachname into l_vorname, l_nachname
  from tab_namen where rowid = rid;
  tlob := 
    '<VORNAME>'   || l_vorname                       || '</VORNAME>'  ||  
    '<NACHNAME>'  || l_nachname                      || '</NACHNAME>' ||  
    '<NAME>'      || l_vorname || ' ' || l_nachname  || '</NAME>';
end;
/
sho err
Die Prozedur als User Datastore registrieren ...

begin
  ctx_ddl.create_preference('names_ds', 'user_datastore');
  ctx_ddl.set_attribute('names_ds', 'procedure', 'namen_uds_proc');
end;
/
sho err
Mit dem Section Group-Objekt wird festgelegt, wie die einzelnen Sections (XML-Tags) von Oracle TEXT behandelt werden sollen ... VORNAME und NACHNAME werden normal behandelt; der zusammengesetzte "NAME" wird als NDATA-Section deklariert.
begin
  ctx_ddl.create_section_group('names_sg', 'xml_section_group');
  ctx_ddl.add_field_section('names_sg', 'VORNAME', 'VORNAME', false);
  ctx_ddl.add_field_section('names_sg', 'NACHNAME', 'NACHNAME', false);
  ctx_ddl.add_ndata_section('names_sg', 'NAME', 'NAME');
end;
/
Schließlich den Index anlegen ...
create index ft_names on tab_namen (nachname)
indextype is ctxsys.context
parameters('
  datastore     names_ds
  section group names_sg
  memory        100m
')
/
Und dann kann man abfragen - zuerst mit "Meier" ...
select * from tab_namen where contains(nachname, 'ndata(name, Meier)')>0
/

        ID VORNAME         NACHNAME
---------- --------------- ---------------
         3 Max             Meier
         4 Moritz          Meyer
         6 Fritz           Maier
Ups ... da fehlt doch einer ... der "Mayer" ist für den NDATA-Algorithmus wohl "zu weit" weg ... Probieren wir noch ein wenig mit dem "Czarski".
select * from tab_namen where contains(nachname, 'ndata(name, Czarsky)')>0
/

        ID VORNAME         NACHNAME
---------- --------------- -------------
         1 Carsten         Czarski

select * from tab_namen where contains(nachname, 'ndata(name, Tsarski)')>0
/

        ID VORNAME         NACHNAME
---------- --------------- -------------
         1 Carsten         Czarski

select * from tab_namen where contains(nachname, 'ndata(name, Tsarsky)')>0
/

Es wurden keine Zeilen ausgewählt
Funktioniert ganz gut, lässt aber doch noch Wünsche offen. Eine Ähnlichkeitssuche wird aber immer Wünsche offenlassen, gerade wenn sie nicht für eine bestimmte Sprache optimiert ist und global funktionieren soll. Die gute Nachricht ist aber, dass NDATA durch einen Thesaurus erweitert werden kann. In diesem Thesaurus können unterschiedliche Schreibweisen von Namen als Synonymbeziehungen hinterlegt und die Treffermenge von NDATA so erweitert werden. Und das Gute ist, dass NDATA dann auch zu den Synonymen ähnliche (!) Namen finden wird. Die Treffermenge wird also nicht nur um die Synonyme selbst, sondern auch um den Synonymen (nach NDATA) ähnliche Namen erweitert.
Wie man einen Thesaurus anlegt und pflegt, ist in diesem Blog-Posting beschrieben. Also erzeugen wir einen Thesaurus wie folgt ...
begin
  ctx_thes.create_thesaurus('namesthes');
  ctx_thes.create_relation('namesthes', 'meyer', 'SYN', 'maier');
  ctx_thes.create_relation('namesthes', 'meyer', 'SYN', 'meier');
  ctx_thes.create_relation('namesthes', 'meyer', 'SYN', 'mayer');
  ctx_thes.create_relation('namesthes', 'czarski', 'SYN', 'czarsky');
end;
/
Als nächstes müssen wir Oracle TEXT sagen, dass es den Thesaurus für NDATA nutzen soll - das geschieht mit einer Wordlist Preference.
begin
  ctx_ddl.create_preference('names_wl', 'BASIC_WORDLIST');
  ctx_ddl.set_attribute('names_wl', 'NDATA_ALTERNATE_SPELLING', 'FALSE');
  ctx_ddl.set_attribute('names_wl', 'NDATA_BASE_LETTER',        'TRUE');
  ctx_ddl.set_attribute('names_wl', 'NDATA_THESAURUS',          'namesthes');
end;
/
Und dann muss der Index gelöscht und neu angelegt werden ...
drop index ft_names
/

create index ft_names on tab_namen (nachname)
indextype is ctxsys.context
parameters('
  datastore     names_ds
  section group names_sg
  wordlist      names_wl
  memory        100m
')
/
Und dann probieren wir die Abfragen erneut ...
select * from tab_namen where contains(nachname, 'ndata(name, Mayer)')>0
/

        ID VORNAME         NACHNAME
---------- --------------- ---------------
         3 Max             Meier
         4 Moritz          Meyer
         5 Franz           Mayer
         6 Fritz           Maier

select * from tab_namen where contains(nachname, 'ndata(name, Tsarsky)')>0
/

        ID VORNAME         NACHNAME
---------- --------------- ---------------
         1 Carsten         Czarski
Voilá - man sieht, dass man die NDATA-Funktionalität sehr gut erweitern kann. Wenn man das von vorneherein in seinen Index einbaut, so kann man den Index aufgrund von Nutzerfeedback "lernen" lassen. Mit einem Namens-Thesaurus lässt sich die NDATA-Funktinalität auf jeden Fall sehr gut abrunden.

Dienstag, 31. Mai 2011

Unscharfe Namenssuche (Name Search) mit NDATA

Vor einiger Zeit als das Feature Name Search mit 11.2.0.2 zur Verfügung gestellt wurde, haben wir schon eine Einführung in das Thema gegeben. Der Blogeintrag dazu ist hier zu finden.
Da mittlerweile einige Migrationen nach 11.2 durchgeführt wurden, wollen wir das Thema noch einmal aufgreifen und einige zusätzliche Informationen dazu geben. Generell ist das Name Searching Feature mit dem neuen Operator NDATA zu verwenden und hilft eine unscharfe Suche durchzuführen. Ich verwende dazu in folgendem Beispiel eine Tabelle mit ca 200 000 Sätzen und ca 8200 verschiedenen Einträgen in einer Spalte ORT. Um Name Searching zu verwenden, benötigen wir einen XML Tag, den ich mit einem MULTICOLUMN DATASTORE wie folgt zur Verfügung stelle.
exec ctx_ddl.drop_preference('name_ds')
begin
  ctx_ddl.create_preference('name_ds', 'MULTI_COLUMN_DATASTORE');
  ctx_ddl.set_attribute('name_ds', 'COLUMNS', 'ort');
end;
/
begin
  ctx_ddl.drop_section_group('name_sg');
end;
/
begin
  ctx_ddl.create_section_group('name_sg', 'BASIC_SECTION_GROUP');
  ctx_ddl.add_ndata_section('name_sg', 'ort', 'ort');
end;
/
Zusätzlich kann auch ALTERNATE SPELLING und BASE LETTER mit NDATA verwendet werden. Hierzu erzeugen wir folgende BASIC_WORDLIST.
exec ctx_ddl.drop_preference('name_wl');
begin
ctx_ddl.create_preference('name_wl', 'BASIC_WORDLIST');
ctx_ddl.set_attribute('name_wl', 'NDATA_ALTERNATE_SPELLING', 'TRUE');
ctx_ddl.set_attribute('name_wl', 'NDATA_BASE_LETTER', 'TRUE');
end;
/
Nun kann der Index erzeugt werden.
CREATE INDEX ns_ort ON basic_lob (ort)
INDEXTYPE IS ctxsys.context
PARAMETERS ('sync (on commit) datastore name_ds 
section group name_sg wordlist name_wl');
SELECT * FROM ctx_index_errors;
Im ersten Versuch suchen wir den Ort "Vilshofen" in Niederbayern - die Schreibweise ist dabei etwas ungewöhnlich. Der Ort wird allerdings schon bei der ersten Abfrage gefunden.
 
SQL> SELECT distinct ort, score(1) FROM basic_lob
     WHERE contains(ort, 'NDATA(ort,Filschthofen)',1) > 0 
     AND score(1)>40;
ORT                                        SCORE(1)
---------------------------------------- ----------
Vilshofen                                        68
Osthofen                                         45
Nun suchen wir einen Ort in Kalifornien, der mit "Santa" beginnt - auch hier mit etwas unüblicher Schreibweise. Zusätzlich können weitere Argumente mitgegeben werden. Das Argument "Proximity" zum Beispiel gibt an, ob die Ähnlichkeit des Suchbegriffs zum tatsächlichen Namen den Score beeinflussen soll.
  
SQL> SELECT distinct ort, score(1) FROM basic_lob
     WHERE contains(ort, 'NDATA(ort,santa kallifornia,, proximity)',1) > 0 
     AND score(1)>40 ORDER BY 2;
ORT                                        SCORE(1)
---------------------------------------- ----------
Santa Clara/Kalifornien                          52
Staat Kalifornien                                52
Santa Maria                                      57
Santa Monica                                     57
santa clara1 california                          61
Santa California                                 83
Santa Kalifornia                                 96

SQL> SELECT distinct ort, score(1) FROM basic_lob 
     WHERE contains(ort, 'NDATA(ort,santa kallifornia)',1) > 0 
     AND score(1)>40 ORDER BY 2;
ORT                                        SCORE(1)
---------------------------------------- ----------
Santa Clara/Kalifornien                          52
Staat Kalifornien                                52
Santa Maria                                      57
Santa Monica                                     57
Santa California                                 83
santa clara1 california                          83
Santa Kalifornia                                 96
Was bedeutet das nun für unseren Index? Schauen wir uns noch kurz die Statistiken an. Klar wird dabei, dass diese umfangreiche Suche auch mit entsprechenden Ressourcen verbunden ist. Die Anzahl der Tokens ist beispielsweise höher als beim Index ohne NDATA. Der nächste Ausschnitt gibt Aufschluss über die Statistik der Tokens. Informationen über die Vorgehensweise findet sich auch in folgendem Blogeintrag.
DROP TABLE ausgabe;
CREATE TABLE ausgabe (resultat CLOB);
declare
    ergebnis clob := null;
  begin
    ctx_report.index_stats(index_name=>'NS_ORT',report=>ergebnis,stat_type=>null);
    insert into ausgabe values (ergebnis);
    commit;
    dbms_lob.freetemporary(ergebnis);
end;
/
set long 32000
set head off
set pagesize 10000
SELECT * FROM ausgabe;
Folgende Ausgabe liefert diese Abfrage:
                       STATISTICS FOR "US"."NS_ORT"
===========================================================================
indexed documents:                                                200,003
allocated docids:                                                 200,003
$I rows:                                                          170,909
---------------------------------------------------------------------------
                             TOKEN STATISTICS
---------------------------------------------------------------------------
unique tokens:                                                     66,955
average $I rows per token:                                           2.55
...
token statistics by type:
  token type:                                             200:NDATA "ORT"
    unique tokens:                                                 66,955
    total rows:                                                   170,909
    average rows:                                                    2.55
    total size:                                     26,653,305 (25.42 MB)
    average size:                                                     398
    average frequency:                                              61.15
Vergleicht man dies mit einer Context Index ohne die Verwendung von NDATA kommt man in unserem Beispiel nur auf ca 6100 eindeutige Tokens und eine Größe von 1,4 MB. Bevor man Name Search verwendet, kann man auch alternativ den FUZZY Operator ausprobieren. Die vollständige Syntax in folgendem Blogeintrag zeigt, wie umfangreich auch mit FUZZY gesucht werden kann.

Montag, 22. Juni 2009

Wie ähnlich soll es sein ...? Ein paar Worte zum FUZZY-Operator

Es ist weitgehend bekannt, dass Oracle TEXT eine Ähnlichkeitssuche mit dem Fuzzy-Operator unterstützt. Die einfachste Variante ist die Verwendung des Fragezeichens ?. Der Fuzzy-Operator ist gut geeignet, um mit etwaigen Rechtschreibfehlern in den Dokumenten umzugehen. Sucht man bspw. nach ?Spatial, so findet der Index auch Dokumente, in denen fälschlicherweise "Sptial" geschrieben wurde.
select dateiname, score(0) from dokumente where contains (content, '?Spatial', 0) > 0
Diese Ähnlichkeitssuche kann übrigens auch parametrisiert werden: Neben dem Fragezeichen steht auch das Schlüsselwort FUZZY zur Verfügung. Oder anders ausgedrückt: Obige SQL-Abfrage ließe sich auch so schreiben:
select dateiname, score(0) from dokumente where contains (content, 'FUZZY(Spatial, 60, 100, N)'), 0) > 0
Und mit diesen Parametern kann man das Verhalten des FUZZY-Operators nun steuern. Der erste Parameter legt fest, wie ähnlich die Tokens im Dokument dem Suchbegriff sein müssen. Erlaubt sind Werte von 1 bis 80. Je niedriger Ihr den Wert ansetzt, desto mehr Begriffe kommen in Frage; desto mehr Dokumente werden also gefunden. Allerdings stellt sich die Frage, wie relevant die Dokumente bei sehr niedrigen Grenzen noch sind.
Der zweite Parameter legt fest, wieviele Werte überhaupt in die Termexpansion einbezogen werden. Dazu kurz einige Worte: Oracle TEXT führt die Fuzzy-Suche über eine Termexpansion durch; es werden also zunächst aus der Token-Tabelle ($I) die ähnlichen Tokens herausgesucht (der erste Parameter legt, wie gesagt, fest, wie ähnlich die Tokens sein müssen). Mit den so gefundenen Tokens wird dann eine ODER Suche durchgeführt.
Mit dem zweiten Parameter legt man also fest, wieviele ähnliche Wörter maximal einbezogen werden sollen. Erlaubt sind Werte zwischen 1 und 5000. Ein Wert von 20 würde bewirken, dass maximal 20 ähnliche Wörter in der Suche berücksichtigt werden, auch wenn anhand des ersten Parameters mehr in Frage kämen. Hier gilt also: Je höher der Wert gesetzt wird, desto mehr Dokumente werden tendenziell gefunden ...
Der letzte Parameter wirkt sich nur auf den Score aus, den ein Dokument im Relevanz-Ranking bekommt. Mit einem W werden die Scores anhand der Ähnlichkeit der Suchwörter gewichtet; mit einem N geschieht das nicht. Ein W führt zu tendenziell höheren Scores.
Mit diesen Parametern könnt Ihr also spielen, um mit der Fuzzy-Suche mehr oder weniger Ergebnisse zu bekommen. Was konkret gebraucht wird, hängt von den Anforderungen des Projekts ab ... zur Verdeutlichung hier nochmals zwei Extrembeispiele. Das erste ist zwar "formal" eine Ähnlichkeitssuche, aber die Parameter "würgen" die Fuzzy-Logik weitgehend ab.
select dateiname, score(0) from dokumente 
where contains(content, 'fuzzy(sptial, 80, 1, W)',0) > 0;
Das zweite bohrt die Grenzen so weit auf, dass sehr viele Dokumente in Frage kommen ...
select dateiname, score(0) from dokumente 
where contains(content, 'fuzzy(sptial, 1, 5000, W)',0) > 0;
Dies lässt sich auch sehr gut mit Query Relaxation verbinden. In einer ersten Stufe würde ohne den Fuzzy-Operator suchen, in einer nächsten Stufe dann mit dem Fuzzy-Operator, aber eher restriktiven Kriterien und danach mit sehr weit gehenden Parametern. Query Relaxation arbeitet die Stufen dann bekanntlich so lange ab, bis genügend Treffer gefunden sind - mehr dazu im Blog Posting.

Beliebte Postings