Möglichkeit zur Darstellung numerischer Schlüssel für einen Rückwärtssuchindex / Sudo Null IT News

Zahlen sind eine ganz besondere Kategorie von Textobjekten. Sie können auf vielfältige Weise dargestellt werden, von der oft ausführlichen und nicht immer konsistenten Reihe abnehmender Zahlen bis hin zu arabischen oder römischen Ziffern, die durch Kommas oder Punkte mit oder ohne Leerzeichen getrennt sind.

Nicht einfacher ist die Situation bei der programmatischen Repräsentation solcher Objekte.

Hey Habr! Mein Name ist Andrey Kovalenko (Keva), ich beschäftige mich mit sprachlichen Aufgaben und erstelle Suchmaschinen. Bei MyOffice leite ich die Entwicklung der Volltextsuche für Unternehmen.

Es gibt zwei Hauptprobleme beim Auffinden numerischer Werte in Textarrays (und Textarrays).

Die erste davon ist die Vielfalt der Möglichkeiten, dieselbe Bedeutung im Text darzustellen. Für die gleiche Zahl könnte es 3600, 3.600, 3,6*10^3 oder einfach “dreitausendsechshundert” sein. Dies wird gelöst, indem sorgfältig vorgeschrieben wird, wie solche Objekte aus dem Text ausgewählt werden können.

Das zweite Problem bezieht sich auf das Auffinden numerischer Intervalle.

Ich erinnere daran, dass Suchmaschinen in der Regel mit dem sogenannten Rückwärtsindex arbeiten, eine hervorragende Metapher dafür ist der alphabetische Index am Ende des Buches: Alle verwendeten Begriffe sind in Normalform angegeben und lexikografisch geordnet – also alphabetisch, und hinter jeder steht eine Seitenzahl, auf der der Begriff vorkommt. Der einzige Unterschied besteht darin, dass dies Informationen koordinieren in Suchmaschinen in der Regel viel mehr. Beispielsweise speichert die Unternehmenssuche MyOffice (Arbeitstitel – baalbek) für jedes Vorkommen eines Wortes in einem Dokument neben der Ordnungszahl auch dessen grammatikalische Form und Bindung an das Markup.

Die Suche beginnt mit der Auswahl des gewünschten Schlüssels im Index-Inhaltsverzeichnis (alphabetischer Index), dann wird die Aufgabe auf die Verarbeitung einer normalen Einzelwortabfrage reduziert.

Und diese Wahl der Tonart oder Tonarten für ein gewünschtes Intervall – zum Beispiel „Der Wert im Feld “Preis” ist nicht größer als 160” oder “Arbeitsvolumen nicht weniger als 2500„Und es wird eine schwierige Aufgabe.

Um im Inhaltsverzeichnis eines Index abgelegt zu werden, ist es notwendig, Zahlenwerte so darzustellen, dass ihr lexikographischer Vergleich mit dem Zahlenwert übereinstimmt.

Offensichtlich hat die Textdarstellung diese Eigenschaft nicht: “2” ist größer als “10”. Auch die Standardform funktioniert nicht: „7e3“ ist kleiner als „8.1e-3“. Wir brauchen einen Datensatz wie „P|M“, wobei P der Exponent ist, | ist das Trennzeichen und M ist die Mantisse.

Die Beispiele aus dem vorherigen Absatz würden als “+0|2”, “+1|1”, “+3|7” und “-3|81” geschrieben. Hier werden schon alle Vergleiche richtig. Die Auswahl der Schlüssel zur Suche nach dem Preis aus dem obigen Beispiel sieht aus wie ein Durchgang durch die numerischen Schlüssel des Index, solange das Ergebnis ihres Vergleichs mit der Zeichenfolge „+2|16“ kleiner oder gleich Null ist.

Problem gelöst? Fast. Irgendwie kann man sich an dieses Zahlenformat gewöhnen. Wenn es keine negativen Zahlen gäbe. Denn -0,7 ist größer als -0,8. Und selbst wenn Sie sie in der Form “P|M” schreiben, erhalten Sie “–1|7” und “–1|8”, und das Ergebnis des lexikografischen Vergleichs ist das Gegenteil des numerischen, weil ‘8’ > ‘7’.

Ersetzen wir negative Zahlen durch ihre Basiskomplemente, in unserem Fall bis 10: “–9|3” und “–9|2”. Hurra? Ist der erste größer als der zweite? Ja. Nun, gleichzeitig wurde endlich die vollständige Unlesbarkeit erreicht.

Halten wir uns also nicht an die ASCII-Darstellung und codieren die Zahlen so, dass sie eindeutig und kompakt sind und den Anforderungen lexikographischer Vergleiche genügen.

Der Einfachheit halber nehmen wir die Basis 16 (Division durch 16 ist eine Bitverschiebung nach rechts um 4). Bringen wir die Zahl zunächst zur Basis 16 in die Standardform: Der ganzzahlige Teil ist eine Zahl von 1 bis 15, der hexadezimale Exponent und der Bruchteil.

Wir schreiben den Wert des Exponenten gemäß dem in utf-8 verwendeten Codierungsprinzip und reservieren maximal 6 Bits. 16^126 Grad scheint eine ziemlich große Zahl zu sein, mehr als ein Googol (10^100, was wiederum mehr ist als die Anzahl der Atome im beobachtbaren Teil des Universums – 10^80). Der ganzzahlige Teil besteht aus 4 weiteren Bits, nur eineinhalb Bytes. Der Bruchteil, also der Rest der graduellen Subtraktion der Mantisse von der ursprünglichen Zahl, wird nacheinander durch 4-Bit-Fragmente zurückgesetzt. Die Schlüsselgröße wird pro Byte ausgerichtet. Und vergessen Sie nicht, alles für negative Zahlen umzukehren. Der Code wird unten sein.

Wir erhalten eine völlig kompakte Darstellung von Zifferntasten, deren letzte Bytes auf Wunsch verworfen werden können, wodurch der Wert bewusst vergröbert wird. Hier sind einige Beispiele:

Bedeutung

Leistung

eines

c0 10

7

c0 70

16

c1 10

255

c1ff

256

c2 10

1048576 = 16^5

c5 10

16^5 + 1

c5 10 00 01

0,1

19 99 99 99 99 99 9a sein

0,03125 = 1/32

b 80

Unten ist der Code (C++) für eine solche Kodierung von Fließkommazahlen. Für ganze Zahlen kann es natürlich etwas einfacher geschrieben werden, ohne arithmetische Funktionen wie pow zu verwenden.

/* * Store – Quartett-Datenschreiber */ template class Store { char buffer[length]; char* Puffer = Puffer; bool Puffer = wahr; public: // schreibe void store( unsigned value ) { if ( !(bupper = !bupper) ) *bufend = (value << 4) | (chfill & 0x0f); sonst { *bufend = (*bufend & 0xf0) | Wert; ++Puffer; } } template void store( unsigned value, Values ​​​​… items ) { return store( value ), store( items… ); } public: auto size() const -> size_t { return bufend – buffer + (buffer ? 0: 1); } auto data() const -> const void* { return buffer; } }; template struct negative_flush: public Store { auto put_mantis( int xpower, int mantis ) -> negative_flush& { if ( xpower >= 0 ) this->store( 0x3 – ((xpower > > 4) & 0x3), 0xf – (xpower & 0x0f) ); sonst this->store( 0x4 | (-xpower >> 4) & 0x03, (-xpower) & 0x0f ); Rückgabe put_nibble (Gottesanbeterin); } auto put_nibble( unsigned u ) -> negative_flush& { return this->store( 0xf – (u & 0xf) ), *this; } Vorlage auto put_nibble( unsigned u, Nibbles … n ) -> negative_flush& { return put_nibble( u ).put_nibble( n… ); } }; template struct positive_flush: public Store { auto put_mantis( int xpower, int mantis ) -> positive_flush& { if ( xpower >= 0 ) this->store( 0x8 | (mantis != 0 ? 0x4 : 0) |((xpower >> 4) & 0x3), xpower & 0x0f ); sonst this->store( 0x8 | (0x3 – ((-xpower >> 4) & 0x3)), (0xf – (-xpower) & 0x0f) ); return this->store( mantis ), *this; } auto put_nibble( unsigned u ) -> positive_flush& { return this->store( u ), *this; } Vorlage auto put_nibble( unsigned u, Nibbles … n ) -> positive_flush& { return put_nibble( u ).put_nibble( n… ); } }; Vorlage static auto make_double_key( Store& flush, const Value& value ) -> const Store& { auto divide = value; automantis = (int)value; autoxpower=(int)0; static_assert( std::is_floating_point::value, “make_double_key( store, value ) würde für Fließkommawerte aufgerufen werden!” ); // sicherstellen, dass der Funktionsaufruf korrekt ist – nur positivesasser( value >= 0.0 ); // 0.0 aussortieren // den ganzzahligen Teil und die Potenz extrahieren if ( value >= 1.0 ) while ( divide >= 16.0 ) { mantis = (divide /= 16.0); ++xpower; } else if ( value != 0.0 ) while ( divide < 1.0 ) {mantis = (divide *= 16.0); --xpower; } Sonst gebe Flush zurück put_mantis( 0, 0 ); bündig put_mantis( xpower, mantis ); if ( mantis != 0 ) { auto dleast = fmod ( value, mantis * pow ( 16, xpower ) ); auto dpower = pow( 16, xpower - 1 ); for ( ; dleast != 0.0; dpower /= 16.0 ) { auto ndigit = (int)(dleast / dpower); bündig put_nibble(ndigit); deast -= ndigit * dpower; } } bündig zurückgeben; }

***

Wenn Sie sich für das Thema morphologische Suche interessieren, schreiben Sie in den Kommentaren darüber – vielleicht werden wir in den folgenden Artikeln näher darauf eingehen und über die Lösung komplexer sprachlicher Probleme im Rahmen der Entwicklung von MyOffice-Produkten sprechen. Und hinterlassen Sie natürlich Ihre Fragen, Kommentare und Vorschläge – wir freuen uns über jedes Feedback von Lesern!

Similar Posts

Leave a Reply

Your email address will not be published.