Avanti & RPN

Cord Veltkamp ve at buch.biblio.etc.tu-bs.de
Fr Aug 28 16:36:05 CEST 1998


Lieber Herr Berger,
ich bezweifle ja, dass diese Diskussson fuer die Liste noch weiter von 
Interesse ist. Aber Sie sollen natuerlich nicht ohne Antwort bleiben.
 
> Das verstehe ich nun nicht unbedingt: RPN ist doch _die_
> Notation mit quasi eingebauter Rekursion:
> 
> A B und C oder D nicht E und F G und oder
> 
> (auf infix:
> 
> ((((A und B) oder C) nicht D) und E) oder (F und G)
> 
> )
> 
> kann von rechts her verarbeitet werden (mit Rekursion)
> aber fast genauso gut von links. Jedenfalls muesste
> doch, egal wie man es haelt, ein rekursiver Algorithmus
> freundlicher mit dem Speicherplatz fuer Zwischenergebnisse
> umgehen als das Zwischenspeichern von bis zu (A..G) 7*32.000
> Satznummern und erst die spaetere Auswertung der Terme.
Vermutlich meinen wir ja dasselbe und streiten uns nur ueber den Begriff 
Rekursion.
Veranschaulichen wir das Problem fuer die Liste mal an dem einfachen 
Beispiel: A*(B+C) oder in unserer Welt:
find PER goethe? and (  TIT weimar? or TIT dichter? )
sieht in RPN aufgeloest so aus: ABC+*
Die Abarbeitung von links nach rechts bedeutet als Avanti-Aktion:
1. suche im Personenregister "goethe?" (max 32.000 Treffer),
    Ergebnismenge auf den Stack schieben.
2. suche im Titelregister "weimar?" -> Stack
3. suche im Titelregister "dichter?" -> Stack
4. "+", die letzten beiden Ergebnismengen vom Stack holen und "oder"- 
Verknuepfung bestmmen. Das Ergebnis kommt auf den Stack.
5. "*", die letzten beiden Ergebnismengen vom Stack holen und "und"- 
Verknuepfung bestmmen. Das Ergebnis kommt auf den Stack.
6. Ergebnismenge vom Stack holen, fertig.

Jeder Suchschritt "weiss" nichts von den bisherigen Ergebnissen und faellt 
dann evt. ueber die 32.000er Grenze. Das ist der Nachteil. Der Vorteil: Der 
Algorithmus wird mit "unbegrenzter" Klammerung fertig.
Bei der vorher implementierten Rekursion wurde jeder Treffer zum Stichwort 
"weimar/dichter" mit der Menge "goethe" verglichen. Dabei musste natuerlich 
der Operator bekannt sein. Bei diesem einfachen Beispiel ist das sicher kein 
Problem. Aber bei Ihrem Beispiel traue ich mir nicht zu, die Vorergebnisse in 
jedem Suchschritt korrekt zu verknuepfen.
Vielleicht laesst sich ja ein Kompromiss einbauen, indem man bei der Suche 
eine Operation in die Zukunft blickt. Aber ueberwiegt der  begrenzte Zugewinn 
an erfolgreichen Abfragen (nur wenn die kleine vor der grossen Treffermenge 
kommt) wirklich den Aufwand? Erhoehen der Grenze waere viel einfacher ;-). 
Und zur Zeit gibt es wirklich dringendere Arbeiten.

Viele Gruesse, Cord Veltkamp



#####################################################################
    Cord Veltkamp                       University Library
    Allegro-C Group                     Universitaetsbibliothek
                                        Pockelsstr. 13
                                        D-38106 Braunschweig
    Email:                              Germany
    c.veltkamp at tu-bs.de                 Tel: +49- 531- 391- 5074
#####################################################################




Mehr Informationen über die Mailingliste Allegro