Eine Volltextsuchmaschine mit ABAP bauen: Ist das möglich?

Aktualisiert: 19. Feb 2020


Teil 1: Die Levenshtein-Distanz


Datenbankselects zu programmieren ist für ABAP-Entwickler eine alltägliche Aufgabe. Seien es Kundenerweiterungen, seien es Reports: Fast bei jeder Entwicklungsaufgabe sieht man sich mit Datenbankabfragen konfrontiert. Für manche Entwickler ist die sogenannte Reportentwicklung gar der Hauptbestandteil ihrer Tätigkeit. Diese Art von Datenbankabfragen zeichnen sich dadurch aus, dass es zu jedem select-Statement ein wohldefiniertes, eindeutiges Ergebnis gibt.

Beispiel: Der Benutzer möchte zu einem Vertriebsbeleg, dessen Nummer er kennt und von dem er weiß, dass er existiert, das Erstellungsdatum ermitteln. Der Entwickler wird dafür folgendes select-Statement erstellen:

select erdat from vbak into lv_erdat where vbeln = p_vbeln.


p_vbeln stellt dabei die Benutzereingabe dar. Wenn die Anwendung keinen Fehler enthält, kann der Benutzer für diese Abfrage genau ein Ergebnis erwarten. Würde die Abfrage kein Ergebnis liefern, so hieße das, dass entweder der Beleg (noch) nicht existiert, d.h. der Benutzer hat sich geirrt, oder dass die Belegdaten inkonsistent wären, d.h. ein Fehler in der Anwendung vorläge.


Anders stellt sich die Situation dar, wenn man es statt mit SAP-Belegen mit Textdokumenten zu tun hat. Textdokumente können entweder im SAP-System entstehen oder von außen in das System eingebracht werden. Man wird eher selten eine Volltextsuche auf Textdokumente ausführen, die im SAP-System entstanden sind, denn es handelt sich ja um Daten, die man auch direkt über Datenbankabfragen ermitteln kann. Dokumente, die von außen in das System kommen unterscheiden sich in einem Punkt fundamental von denen, die aus Systemdaten erstellt wurden: Diese Dokumente enthalten statistische Fehler.

Beispiel: Ein Lieferant sendet per Post eine Rechnung. Die Rechnung wird beim Empfänger eingescannt und in einem Filesystemordner abgelegt, um später durch einen OCR-Server weiterverarbeitet zu werden. OCR-Algorithmen arbeiten häufig mit neuronalen Netzen und liefern Ergebnisse, die mit einem zufälligen Fehler behaftet sind. In den Ergebnisdateien des OCR-Servers kann man nach Wörtern oder mehreren Wörtern suchen. Im Unterschied zur Datenbanksuche liefert diese Suche kein wohldefiniertes Ergebnis. Schickt der Lieferant etwa eine Rechnung mit der Artikelnummer 12345, so kann es sein, dass der OCR-Algorithmus 12349 erkennt. Sucht man nun nach 12345, so würde eine Gleichheitsprüfung der Strings fehlschlagen und die Suche würde kein Ergebnis liefern. Dennoch würde der Benutzer ein Ergebnis erwarten.

Das bedeutet, dass man ein Maß für Ähnlichkeit von Wörtern - oder allgemeiner Strings - benötigt. Bekannt sind der Hamming-Abstand und die Levenshtein-Distanz oder auch Edit-Distanz. Der Hamming-Abstand zählt im wesentlichen die Anzahl der verschiedenen Zeichen in der Wörtern. Die Levenshtein-Distanz zählt die minimale Anzahl von Edit-Operationen, die nötig sind, um das eine Wort in das andere zu überführen. Dabei sind die Edit-Operationen

Die Levenshtein-Distanz hat die Eigenschaften einer Metrik, erfüllt also insbesondere die Dreiecksungleichung. Dass die Dreiecksungleichung erfüllt ist, folgt direkt aus der Minimalität der Levenshtein-Distanz.

Der Levenshtein Algorithmus wird häufig implementiert mit Hilfe sogenannter dynamischer Programmierung. Dazu ordnet man die zu vergleichenden Wörter in einem Tableau an wie im folgenden dargestellt:












Die zweite Zeile liest man folgendermaßen: Um ein leeres Wort in "j" abzubilden, benötigt man eine Operation, nämlich das Einfügen von "j". Um ein leeres Wort in "ju" abzubilden, benötigt man 2 Operation, nämlich Einfügen von "j" und Einfügen von "u" usw.

Betrachten wir das 5-5-Element der Matrix. Das 5-5-Element der Matrix hat den Wert 1, weil das Zeichen "l" durch "n" ersetzt werden muss. Allgemein kommt das Element (i,j) zustande als


min{Element(i-1,j-1)+1, Element(i,j-1)+1,Element(i-1,j)+1}, falls die Zeichen verschieden sind

und

Element(i-1,j-1), falls die Zeichen gleich sind.


Verfügt man über eine ABAP-Implementierung von M x N Matrizen, so lässt der Levenshtein-Algorithmus einfach in ABAP implementieren.


Hier eine Beispielimplementierung:


METHOD calc_levenshtein_dist.

DATA: lo_matrix TYPE REF TO /cow/cl_ase_matrix_int, lo_vektor_s1 TYPE REF TO /cow/cl_ase_matrix_char1, lo_vektor_s2 TYPE REF TO /cow/cl_ase_matrix_char1, m TYPE int4, n TYPE int4, k TYPE int4, l TYPE int4, a TYPE int4, b TYPE int4, r TYPE int4, s TYPE int4, r_ TYPE int4, s_ TYPE int4, o TYPE int4, p TYPE int4, c TYPE c, lv_value TYPE int4, lv_value_0_0 TYPE int4, lv_value_1_0 TYPE int4, lv_value_0_1 TYPE int4, lv_costs TYPE int4, lv_prefixlen TYPE int4.

o = STRLEN( iv_s1 ). p = STRLEN( iv_s2 ).

m = o + 1.

n = p + 1.

* Create matrix CREATE OBJECT lo_matrix EXPORTING iv_m = m iv_n = n. * Fill first column DO m TIMES. k = sy-index. l = k - 1. lo_matrix->set_i_j( iv_i = k iv_j = 1 iv_value = l ). ENDDO.

* Fill first row DO n TIMES. k = sy-index. l = k - 1. lo_matrix->set_i_j( iv_i = 1 iv_j = k iv_value = l ). ENDDO.

* Create the word s1 vector CREATE OBJECT lo_vektor_s1 EXPORTING iv_m = m iv_n = 1. * Set space lo_vektor_s1->set_i_j( iv_i = 1 iv_j = 1 iv_value = space ). * Fill the vector DO o TIMES. k = sy-index. l = k - 1. c = iv_s1+l(1). k = k + 1. lo_vektor_s1->set_i_j( iv_i = k iv_j = 1 iv_value = c ). ENDDO.

* Create the word s2 vector CREATE OBJECT lo_vektor_s2 EXPORTING iv_m = 1 iv_n = n. * Set space on first pos lo_vektor_s2->set_i_j( iv_i = 1 iv_j = 1 iv_value = space ). * Fill the vector DO p TIMES. k = sy-index. l = k - 1. c = iv_s2+l(1). k = k + 1. lo_vektor_s2->set_i_j( iv_i = 1 iv_j = k iv_value = c ). ENDDO.

* Fill the rows DO o TIMES. r = sy-index. r_ = sy-index + 1. DO p TIMES. s = sy-index. s_ = sy-index + 1.

IF lo_vektor_s1->get_i_j( iv_i = r_ iv_j = 1 ) NE lo_vektor_s2->get_i_j( iv_i = 1 iv_j = s_ ). lv_value_0_0 = lo_matrix->get_i_j( iv_i = r iv_j = s ). lv_value_1_0 = lo_matrix->get_i_j( iv_i = r_ iv_j = s ). lv_value_0_1 = lo_matrix->get_i_j( iv_i = r iv_j = s_ ). lv_value = /cow/cl_ase_util=>min_3( iv_1 = lv_value_0_0 iv_2 = lv_value_1_0 iv_3 = lv_value_0_1 ) + 1. lo_matrix->set_i_j( iv_i = r_ iv_j = s_ iv_value = lv_value ). ELSE. lv_value = lo_matrix->get_i_j( iv_i = r iv_j = s ). lo_matrix->set_i_j( iv_i = r_ iv_j = s_ iv_value = lv_value ). ENDIF. ENDDO. ENDDO.

rv_ = lo_matrix->get_i_j( iv_i = m iv_j = n ).

ENDMETHOD.


Wer diese Implementierung verwenden möchte, muss lediglich die Matrixklassen durch eigene ersetzen. Die Matrizen werden nur zum Speichern der Werte verwendet. D.h. es ist keine Implementierung von Matrixmultiplikationen o.ä. nötig.

Man mache sich klar, dass der Algorithmus eine Laufzeit der Größenordnung O(m*n) hat, wenn die zwei Wörter n bzw. m Zeichen enthalten.

Damit haben wir den ersten Schritt für die Implementierung einer Volltextsuche in ABAP getan. Wir können die Ähnlichkeit von zwei Wörtern messen. Im zweiten Teil dieses Blogbeitrags werden wir untersuchen, welche Datenbankstrukturen nötig sind, um Wörter und Dokumente zu speichern und wie man performant auf diesen Strukturen suchen kann, obwohl der Levenshtein-Algorithmus eine Laufzeit von O(m*n) hat.


Teil 2: Erzeugen des VP-Trees

Um etwa schnelle Volltextsuchen auf eingescannten Dokumenten zu ermöglichen, müssen die Dokumente indiziert werden. D.h. wir speichern alle Wörter der Dokumente in einer DB-Tabelle, der Wörterbuchtabelle und die Dokumente selbst z.B. in einem Archiv. Die Beziehung Wort ↔ Dokument ID speichern wir in einer eigenen DB-Tabelle, der Wort↔Dokumentmatrix.

Wörterbuchtabelle:

Wort↔Dokumentmatrix:

Der Prozess des Dokumentindizierens ist simpel. Für jedes eingescannte Dokument, das den OCR Prozess durchlaufen hat, wird das Dokument im Archiv abgelegt. Dann werden die extrahierten Wörter (nach translate to upper case) im Wörterbucg gespeichert und die Relationen Wort↔Dokument in der Wort↔Dokumentmatrix. Eine ähnliche Vorgehensweise funktioniert auch für Inhalte von Datenbanktabellen. In unserem Umfeld hat es immer eine spezielle Bedeutung, wenn wir von "Prozess" reden. Ein Prozess ist jeweils ein Prozess im Sinne des Universal Process Tools oder einer Kette solcher Prozesse. Natürlich kann dieses Prinzip auch ohne Universal Process Tool angewendet werden.

Mit Hilfe der Levenshtein Distanz könnten nun bereits Ähnlichkeitssuchen auf dem Wörterbuch stattfinden. Über die Wort↔Dokumentmatrix können dann die zugehörigen Dokumente ermittelt werden. Leider ist der Wortvergleich per Edit-Distance sehr inperformant aus oben genannten Gründen. Man mache sich klar, dass bei einer Suche das gesuchte Wort zunächst mit allen Wörtern des Wörterbuchs verglichen werden muss. Daher ist es wünschenswert, das Wörterbuch möglichst klein zu halten. Dafür gibt es verschiedene Verfahren, etwa alle Stop Words eliminieren, nur Großschreibung verwenden, auf den Wortstamm reduzieren (keine gebeugten Wörter) usw. Darauf gehen wir nicht weiter ein. All diese Verfahren reichen dennoch nicht aus, generisch eine performante Suche sicherzustellen.

Um eine performante Suche zu erreichen, indizieren wir die Wörter im Wörterbuch durch einen sogenannten VP-Tree (Vantage Point Tree). Die Idee des VP-Trees besteht darin, eine Teilmenge eines metrischen Raums so zu partitionieren, dass man meistens entweder nur innerhalb eines metrischen Balls um einen gegebenen Punkt (vantage point) suchen muss oder nur außerhalb. Sind die Punkte innerhalb des Balles und außerhalb des Balles etwa gleich verteilt, erreicht man so annähernd eine binäre Suche, deren Kosten log(n) sind im Gegensatz zu n bei der linearen Suche. In unserem Fall ist die Metrik d(wort1, wort2) := levenshtein_dist(wort1,wort2). Der VP-Tree wird dann folgendermaßen aufgebaut:

1. Wir suchen zufällig ein Wort w1 aus dem Wörterbuch aus und berechnen d(w1,w) für alle w im Wörterbuch ungleich w1. Wir wählen einen Radius r, so dass etwa die Hälfte aller Wörter w im Ball mit Radius r um w1 liegt, und damit die andere Hälfte außerhalb des Balles liegt (Medianradius). Alle Wörter, die innerhalb des Balles liegen, werden zukünftig im linken Zweig unter dem ersten VP liegen, während die anderen im rechten Zweig unter dem ersten VP liegen. Die nächsten zwei VPs (den rechten und den linken) erhalten wir, indem wir das Verfahren auf die beiden disjunkten Teilmengen anwenden, d.h. wir suchen jeweils VPs für alle Punkte im Ball um den ersten VP und für alle Punkte außerhalb des Balles um den ersten VP. Dieses Verfahren interieren wir, bis keine Punkte mehr übrig sind. Das Ergebnis speichern wir in unserer VP-Tabelle.

VP-Tree Tabelle:

Im folgenden das komplette Listing der Vantage Tree Builder Klasse:


class /COW/CL_ASE_VP_TREE_BUILDER definition

public

final

create public .


*"* public components of class /COW/CL_ASE_VP_TREE_BUILDER

*"* do not include other source files here!!!

public section.


methods BUILD

raising

/COW/CX_ROOT .

methods CONSTRUCTOR

importing

!IV_SEARCH_AREA type /COW/ASE_SEARCH_AREA .

methods CREATE_NODE

importing

!IV_PA_NODE_ID type /COW/NODE_ID

!IV_LEFT_RIGHT type /COW/ASE_LEFT_RIGHT_FLAG

changing

!CT_WORDS type /COW/ASE_T_WORD_S

raising

/COW/CX_ROOT .

class-methods STATIC_NODE_ID_CREATE

returning

value(RV_) type CHAR32 .

protected section.

*"* protected components of class /COW/CL_ASE_VP_TREE_BUILDER

*"* do not include other source files here!!!

private section.

*"* private components of class /COW/CL_ASE_VP_TREE_BUILDER

*"* do not include other source files here!!!


data MV_SEARCH_AREA type /COW/ASE_SEARCH_AREA .

data MT_WORDS type /COW/ASE_T_WORD_S .


methods RESET .

methods CREATE_ROOT_NODE

raising

/COW/CX_ROOT .

class-methods DIST_LIST_CALC_MEAN

importing

!IT_DIST type /COW/ASE_T_DISTANCE

returning

value(RV_) type /COW/ASE_RATIONAL .

class-methods DIST_LIST_CALC_VARIANCE

importing

!IT_DIST type /COW/ASE_T_DISTANCE

returning

value(RV_) type /COW/ASE_RATIONAL .

methods WORD_CALC_VARIANCE

importing

!IV_WORD type STRING

!IT_WORDS type /COW/ASE_T_WORD_S

returning

value(RV_) type /COW/ASE_RATIONAL

raising

/COW/CX_ROOT .

methods GET_RANDOM_WORD

importing

!IT_WORDS type /COW/ASE_T_WORD_S

returning

value(RV_) type /COW/ASE_WORD .

methods GET_VARIANT_WORD

importing

!IT_WORDS type /COW/ASE_T_WORD_S

returning

value(RV_) type /COW/ASE_WORD .

ENDCLASS.




CLASS /COW/CL_ASE_VP_TREE_BUILDER IMPLEMENTATION.



METHOD build.


me->reset( ).


me->create_root_node( ).


ENDMETHOD.



METHOD constructor.

mv_search_area = iv_search_area.

ENDMETHOD.



METHOD create_node.


DATA: lv_word_s TYPE string,

lv_word_s1 TYPE string,

lv_word_s2 TYPE string,

lv_word_s3 TYPE string,

lv_median TYPE int4,

lv_median_low TYPE int4,

lv_median_up TYPE int4,

lv_median_opt TYPE int4,

ls_node TYPE /cow/ase_vp_tree,

lv_len TYPE int4,

lv_from TYPE int4,

lt_words_left TYPE /cow/ase_t_word_s,

lt_words_right TYPE /cow/ase_t_word_s,

lv_dist TYPE int4,

lv_tabix TYPE sy-tabix,

lv_var1 TYPE /cow/ase_rational,

lv_var2 TYPE /cow/ase_rational,

lv_var3 TYPE /cow/ase_rational,

lv_var TYPE /cow/ase_rational,

lv_median_dist_up TYPE int4,

lv_median_dist_low TYPE int4,

lv_string TYPE string.


FIELD-SYMBOLS: <ls_word> TYPE /cow/ase_s_word_s.


lv_word_s = me->get_random_word( ct_words ).

* lv_word_s2 = me->get_random_word( ct_words ).

* lv_word_s3 = me->get_random_word( ct_words ).

*

* lv_var1 = me->word_calc_variance( iv_word = lv_word_s1 it_words = ct_words ).

* lv_var2 = me->word_calc_variance( iv_word = lv_word_s2 it_words = ct_words ).

* lv_var3 = me->word_calc_variance( iv_word = lv_word_s3 it_words = ct_words ).

*

* lv_var = /cow/cl_ase_util=>max_3_rational( iv_1 = lv_var1 iv_2 = lv_var2 iv_3 = lv_var3 ).

*

* CASE lv_var.

* WHEN lv_var1.

* lv_word_s = lv_word_s1.

* WHEN lv_var2.

* lv_word_s = lv_word_s2.

* WHEN lv_var3.

* lv_word_s = lv_word_s3.

* ENDCASE.

*

* lv_word_s = me->get_variant_word( ct_words ).

IF lv_word_s IS INITIAL.

RETURN.

ENDIF.

* Calc distance for all words in set

LOOP AT ct_words ASSIGNING <ls_word>.

lv_string = <ls_word>-word.

<ls_word>-radius = /cow/cl_ase_util=>calc_levenshtein_dist( iv_s1 = lv_word_s iv_s2 = lv_string ).

ENDLOOP.

* Sort

SORT ct_words BY radius ASCENDING.

* Get length

lv_len = LINES( ct_words ).

lv_median = lv_len / 2.

READ TABLE ct_words INDEX lv_median ASSIGNING <ls_word>.

IF sy-subrc NE 0.

* ToDo

ENDIF.

lv_dist = <ls_word>-radius.


* Get first with this distance

LOOP AT ct_words ASSIGNING <ls_word> TO lv_median.

lv_tabix = sy-tabix.

IF <ls_word>-radius = lv_dist.

EXIT.

ENDIF.

ENDLOOP.

lv_median_low = lv_tabix - 1.


* Get last with this distance

LOOP AT ct_words ASSIGNING <ls_word> FROM lv_median.

lv_tabix = sy-tabix.

IF <ls_word>-radius > lv_dist.

EXIT.

ENDIF.

ENDLOOP.

lv_median_up = lv_tabix - 1.


lv_median_dist_up = lv_median_up - lv_median.

lv_median_dist_low = lv_median - lv_median_low.

IF lv_median_dist_up < lv_median_dist_low.

lv_median_opt = lv_median_up.

ELSE.

lv_median_opt = lv_median_low.

ENDIF.

* Get the word

READ TABLE ct_words INDEX lv_median_opt ASSIGNING <ls_word>.

lv_dist = <ls_word>-radius.


* Add node

ls_node-search_area = mv_search_area.

ls_node-node_id = static_node_id_create( ).

ls_node-pa_node_id = iv_pa_node_id.

ls_node-word = lv_word_s.

ls_node-radius = lv_dist.

ls_node-left_right = iv_left_right.

IF LINES( ct_words ) = 1.

ls_node-is_leaf = abap_true.

ENDIF.

* Remove the center point

DELETE ct_words INDEX 1.

* Update index

MODIFY /cow/ase_vp_tree FROM ls_node.

COMMIT WORK.


lv_median_opt = lv_median_opt - 1.


IF lv_median_opt > 0.

* Split set

LOOP AT ct_words ASSIGNING <ls_word> FROM 1 TO lv_median_opt.

APPEND <ls_word> TO lt_words_left.

ENDLOOP.

ENDIF.


lv_from = lv_median_opt + 1.

IF LINES( ct_words ) GE lv_from.

LOOP AT ct_words ASSIGNING <ls_word> FROM lv_from.

APPEND <ls_word> TO lt_words_right.

ENDLOOP.

ENDIF.



CLEAR ct_words.


DATA: lo_left TYPE REF TO /cow/cl_ase_vp_tree_builder,

lo_right TYPE REF TO /cow/cl_ase_vp_tree_builder.


IF LINES( lt_words_left ) > 0.

me->create_node( EXPORTING iv_pa_node_id = ls_node-node_id

iv_left_right = 'L'

CHANGING ct_words = lt_words_left ).

ENDIF.


IF LINES( lt_words_right ) > 0.

me->create_node( EXPORTING iv_pa_node_id = ls_node-node_id

iv_left_right = 'R'

CHANGING ct_words = lt_words_right ).

ENDIF.


ENDMETHOD.



METHOD create_root_node.


SELECT word length FROM /cow/ase_words INTO CORRESPONDING FIELDS OF TABLE mt_words

WHERE search_area = mv_search_area.


SORT mt_words BY word.

DELETE ADJACENT DUPLICATES FROM mt_words.


me->create_node( EXPORTING iv_pa_node_id = space

iv_left_right = 'C'

CHANGING ct_words = mt_words ).


ENDMETHOD.



METHOD dist_list_calc_mean.


DATA: lv_lines TYPE int4,

lv_dist TYPE int4.


FIELD-SYMBOLS: <lv_dist> TYPE int4.


lv_lines = LINES( it_dist ).


IF lv_lines = 0.

RETURN.

ENDIF.


LOOP AT it_dist ASSIGNING <lv_dist>.

lv_dist = lv_dist + <lv_dist>.

ENDLOOP.


rv_ = lv_dist / lv_lines.


ENDMETHOD.



METHOD dist_list_calc_variance.


DATA: lv_lines TYPE int4,

lv_dist TYPE int4,

lv_var TYPE int4.

DATA: lv_mean TYPE /cow/ase_rational.


FIELD-SYMBOLS: <lv_dist> TYPE int4.


lv_lines = LINES( it_dist ).

IF lv_lines = 0.

RETURN.

ENDIF.


lv_mean = /cow/cl_ase_vp_tree_builder=>dist_list_calc_mean( it_dist ).


LOOP AT it_dist ASSIGNING <lv_dist>.

lv_var = lv_var + ( <lv_dist> - lv_mean ) * ( <lv_dist> - lv_mean ).

ENDLOOP.


rv_ = lv_var / lv_lines.

ENDMETHOD.



METHOD get_random_word.


DATA: lv_lines TYPE int4,

lv_seed TYPE int4,

lo_random TYPE REF TO cl_abap_random,

lv_random TYPE int4.


FIELD-SYMBOLS: <ls_words> TYPE /cow/ase_s_word_s.


lv_lines = LINES( it_words ).


IF lv_lines < 1.

RETURN.

ENDIF.


lv_seed = cl_abap_random=>seed( ).


lo_random = cl_abap_random=>create( lv_seed ).


lv_random = lo_random->intinrange( low = 1 high = lv_lines ).