Kollation

In diesem Artikel geht es um Zusammenstellung in Bibliothek, Informationen und Informatik. Für andere Verwendungen siehe Zusammenstellung (Disambiguation).

Kollation ist die Zusammenstellung schriftlicher Informationen in eine Standardauftrag. Viele Zusammenstellungssysteme basieren auf numerische Ordnung oder alphabetischer Reihenfolge, oder Erweiterungen und Kombinationen davon. Zusammenstellung ist ein grundlegendes Element des meisten Büros Aktensysteme, Bibliothekskataloge, und Nachschlagewerke.

Zusammenstellung unterscheidet sich von Einstufung da sind die Klassen selbst nicht unbedingt bestellt. Selbst wenn die Reihenfolge der Klassen irrelevant ist, können die Kennungen der Klassen Mitglieder eines geordneten Satzes sein, was a zulässt Sortieren von Algorithmus die Gegenstände nach Unterricht arrangieren.

Formell spricht eine Kollationsmethode typischerweise a Gesamtbestellung auf einer Reihe möglicher Kennungen, die als Sortschlüssel bezeichnet werden, die folglich a erzeugen Gesamtvorbestellung Auf dem Satz von Informationen (Elemente mit derselben Kennung werden in keiner definierten Reihenfolge festgelegt).

Ein Zusammenstellungsalgorithmus wie der UNICODE COLLATION ALGORITHM definiert eine Reihenfolge durch den Prozess des Vergleichs von zwei gegebenen Charakterzeichenfolgen und entscheiden, welche vor dem anderen kommen sollte. Wenn auf diese Weise eine Bestellung definiert wurde, kann ein Sortieralgorithmus verwendet werden, um eine Liste einer beliebigen Anzahl von Elementen in diese Reihenfolge einzulegen.

Der Hauptvorteil der Kollation besteht darin, dass es einem Benutzer schnell und einfach macht, ein Element in der Liste zu finden oder zu bestätigen, dass es in der Liste fehlt. In automatischen Systemen kann dies mit a erfolgen binärer Suchalgorithmus oder Interpolationssuche; Die manuelle Suche kann unter Verwendung eines ungefähr ähnlichen Verfahrens durchgeführt werden, obwohl dies häufig unbewusst durchgeführt wird. Andere Vorteile sind, dass man leicht die ersten oder letzten Elemente in der Liste finden kann (höchstwahrscheinlich bei numerisch sortierten Daten nützlich) oder Elemente in einem bestimmten Bereich (bei numerischen Daten wieder nützlich Alphabetisch geordnete Daten, wenn man nur die ersten Briefe des gesuchten Elements oder der gesuchten Elemente sicher sein kann.

Bestellung

Numerisch und chronologisch

Saiten, die dargestellt werden Zahlen kann basierend auf den Werten der Zahlen sortiert werden, die sie darstellen. Zum Beispiel "–4", "2,5", "10", "89", "30.000". Beachten Sie, dass die reine Anwendung dieser Methode nur eine teilweise Bestellung für die Zeichenfolgen liefern kann, da verschiedene Zeichenfolgen dieselbe Zahl darstellen können (wie bei "2" und "2,0" oder wann wissenschaftliche Schreibweise wird verwendet, "2E3" und "2000").

Ein ähnlicher Ansatz kann mit Zeichenfolgen verfolgt werden, die dargestellt werden Termine oder andere Gegenstände, die chronologisch oder auf andere natürliche Weise bestellt werden können.

Alphabetisch

Hauptartikel: Alphabetischer Reihenfolge

Alphabetischer Reihenfolge ist die Grundlage für viele Kollationssysteme, bei denen Informationsgegenstände durch Zeichenfolgen identifiziert werden, die hauptsächlich aus bestehen Briefe von einem Alphabet. Die Reihenfolge der Saiten hängt von der Existenz einer Standardordnung für die Buchstaben des betreffenden Alphabets ab. (Das System ist nicht auf Alphabete im strengen technischen Sinne beschränkt; Sprachen, die a verwenden Silbenschrift oder Abugida, zum Beispiel Cherokee, kann das gleiche Bestellprinzip verwenden, sofern es eine festgelegte Bestellung für die verwendeten Symbole gibt.)

Um zu entscheiden, welches der zwei Saiten in alphabetischer Reihenfolge an erster Stelle steht, werden ihre ersten Buchstaben zunächst verglichen. Die Zeichenfolge, deren erster Buchstabe früher im Alphabet erscheint, steht in alphabetischer Reihenfolge an erster Stelle. Wenn die ersten Buchstaben gleich sind, werden die zweiten Buchstaben verglichen und so weiter, bis die Bestellung entschieden ist. (Wenn eine Zeichenfolge keine Buchstaben ausgeht, wird es als zuerst angesehen; zum Beispiel "Wagen" kommt vor "Carthorse".) Das Ergebnis der Anordnung einer Reihe von Saiten in alphabetischer Reihenfolge ist, dass Wörter mit demselben ersten gleich Der Brief wird zusammengefasst und innerhalb eines solchen Gruppenwörter mit den gleichen ersten beiden Buchstaben zusammengegeben und so weiter.

Großbuchstaben werden typischerweise als äquivalent zu ihren entsprechenden Kleinbuchstaben behandelt. (Für alternative Behandlungen in computergestützten Systemen siehe Automatisierte Zusammenstellung, unter.)

Bestimmte Einschränkungen, Komplikationen und spezielle Konventionen können gelten, wenn alphabetische Reihenfolge verwendet wird:

  • Wenn Saiten enthalten Räume oder andere Wortteiler, die Entscheidung muss getroffen werden, ob diese Teilnehmer ignorieren oder sie als Symbole vor allen anderen Buchstaben des Alphabets behandeln sollen. Wenn zum Beispiel der erste Ansatz verfolgt wird, wird "Parkplatz" nach "Carbon" und "Karpfen" (wie es so wäre, wenn er "Parkplatz" geschrieben worden wäre), während im zweiten Ansatz "Parkplatz" vor diesen kommt zwei Wörter. Die erste Regel wird in vielen verwendet (aber nicht alle) Wörterbücher, der zweite in Telefonverzeichnisse (so dass Wilson, Jim K, mit anderen Leuten namens Wilson, Jim und nicht nach Wilson, Jimbo, erscheint).
  • Abkürzungen können so behandelt werden, als wären sie vollständig geschrieben. Zum Beispiel Namen, die "St." enthalten (kurz für das englische Wort Heilige) werden oft so angeordnet, als wären sie als "Heiliger" ausgeschrieben. Es gibt auch eine traditionelle Konvention auf Englisch, die den Nachnamen beginnt MC und M' werden so aufgeführt, als ob diese Präfixe geschrieben wären Mac.
  • Saiten, die persönliche Namen darstellen Vorname kommt zuerst. Zum Beispiel sollten Juan Hernandes und Brian O'Leary als "Hernandes, Juan" und "O'Leary, Brian" sortiert werden, auch wenn sie nicht so geschrieben sind.
  • Sehr häufige anfängliche Wörter, wie z. Das Auf Englisch werden oft zu Sortierzwecken ignoriert. So Das Leuchten würde sortiert sein als "glänzend" oder "glänzend, das".
  • Wenn einige der Saiten enthalten Ziffern (oder andere Nicht-Letter-Zeichen), verschiedene Ansätze sind möglich. Manchmal werden solche Charaktere so behandelt, als ob sie vor oder nach allen Buchstaben des Alphabets kamen. Eine andere Methode besteht darin, dass Zahlen alphabetisch sortiert werden, wie sie geschrieben werden würden: Zum Beispiel 1776 würde sortiert, als ob "siebzehn sechsundsiebzig" geschrieben hätte, und 24 Heures du Mans als ob "Vingt-Quatre ..." (Französisch für "vierundzwanzig"). Wenn Ziffern oder andere Symbole als spezielle grafische Formen von Buchstaben verwendet werden, wie in 1337 zum Leet oder Se7en Für den Filmtitel SiebenSie können sortiert werden, als wären sie diese Briefe.
  • Sprachen haben unterschiedliche Konventionen für die Behandlung Modifizierte Buchstaben und bestimmte Buchstabenkombinationen. Zum Beispiel in Spanisch der Buchstabe ñ wird als Grundbrief folgt behandelt n, und die Digraphen CH und ll wurden früher (bis 1994) als grundlegende Briefe behandelt c und l, obwohl sie jetzt als Zwei-Buchstaben-Kombinationen alphabetisiert werden. Eine Liste solcher Konventionen für verschiedene Sprachen finden Sie unter Alphabetische Ordnung § Sprachspezifische Konventionen.

In mehreren Sprachen haben sich die Regeln im Laufe der Zeit geändert, und so können ältere Wörterbücher eine andere Reihenfolge verwenden als moderne. Darüber hinaus kann die Zusammenfassung von der Verwendung abhängen. Zum Beispiel Deutsch Wörterbücher und Telefonverzeichnisse Verwenden Sie verschiedene Ansätze.

Radikal-and-thropp-Sortierung

Siehe auch Indizierung chinesischer Zeichen

Eine andere Form der Zusammenstellung ist radikal-and-thropp-Sortierung, verwendet für nicht alphabetische Schreibsysteme wie die Hanzi von Chinesisch und die Kanji von japanisch, deren Tausende von Symbolen sich der Bestellung durch Konvention widersetzen. In diesem System werden gemeinsame Komponenten von Zeichen identifiziert; Diese nennt man Radikale in chinesischen und logografischen Systemen, die von Chinesen abgeleitet sind. Die Zeichen werden dann nach ihrem primären Radikal gruppiert und dann nach Anzahl der Stiftstriche innerhalb von Radikalen geordnet. Wenn es kein offensichtliches radikaler oder mehr als ein Radikal gibt, regelt die Konvention, die für die Zusammenstellung verwendet wird. Zum Beispiel wird der chinesische Charakter 妈 (was "Mutter") als sechs Takt-Charakter unter dem dreistabigen primären Radikal 女 sortiert.

Das radikale und Schlaganfall-System ist im Vergleich zu einem alphabetischen System umständlich, in dem einige Zeichen eindeutig sind. Die Auswahl, welche Komponenten eines Logographen separate Radikale umfassen und welche radikal primär ist, ist nicht eindeutig. Infolgedessen ergänzen logografische Sprachen häufig die radikale und Schlaganfall-Ordnung mit alphabetischer Sortierung einer phonetischen Umwandlung der Logographen. Zum Beispiel das Kanji -Wort Tokio (東京) kann sortiert werden, als ob es in den japanischen Charakteren der Hiragana Silbe als "to-u-ki-yo-U "(とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう とうきょう).

Darüber hinaus im Großarina, im Großraum China, Nachname -Schlaganfallbestellung ist eine Konvention in einigen offiziellen Dokumenten, bei denen die Namen der Menschen ohne Hierarchie aufgeführt sind.

Automatisierung

Wenn Informationen in digitalen Systemen gespeichert werden, kann die Kollektion zu einem automatisierten Prozess werden. Es ist dann notwendig, eine angemessene Zusammenfassung umzusetzen Algorithmus Dadurch können die Informationen für die betreffende Anwendung zufriedenstellend sortiert werden. Oft ist es das Ziel, eine alphabetische oder numerische Reihenfolge zu erreichen, die den Standardkriterien wie in den vorhergehenden Abschnitten beschrieben folgt. Allerdings sind nicht alle diese Kriterien leicht zu automatisieren.[1]

Die einfachste Art der automatisierten Zusammenfassung basiert auf den numerischen Codes der Symbole in a Zeichensatz, wie zum Beispiel ASCII Codierung (oder eines von ITS Supersets wie zum Beispiel Unicode), wobei die Symbole in zunehmender numerischer Reihenfolge ihrer Codes angeordnet sind und diese Reihenfolge gemäß den Grundprinzipien der alphabetischen Reihenfolge auf Zeichenfolgen ausgedehnt werden (mathematisch gesehen, Lexikografische Ordnung). Ein Computerprogramm kann also die Charaktere behandeln a, b, C, d, und $ wie bestellt $, C, a, b, d (Die entsprechenden ASCII -Codes sind $ = 36, a = 97, b = 98, C = 67 und d = 100). Daher beginnt Saiten mit C, M, oder Z würde vor Strings mit niedrigerer Fall sortiert werden a, busw. Dies wird manchmal genannt Asciibetische Ordnung. Dies weicht von der alphabetischen Standardordnung ab, insbesondere aufgrund der Bestellung von Großbuchstaben vor allen niedrigeren Case (und möglicherweise der Behandlung von Räumen und anderen Nicht-Letter-Zeichen). Es wird daher häufig mit bestimmten Änderungen angewendet, die offensichtlichste Fallumwandlung (oft in Großbuchstaben, aus historischen Gründen[Anmerkung 1]) Vor dem Vergleich der ASCII -Werte.

In vielen Kollationsalgorithmen basiert der Vergleich nicht auf den numerischen Codes der Zeichen, sondern auf dem Vergleich Sammelsequenz - Eine Sequenz, in der angenommen wird, dass die Zeichen zum Zwecke der Zusammenfassung und anderen Bestellregeln kommen, die der angegebenen Anwendung geeignet sind. Dies kann dazu dienen, die korrekten Konventionen für die alphabetische Bestellung in der fraglichen Sprache anzuwenden und ordnungsgemäß mit unterschiedlichen Gehäusebuchstaben zu behandeln. Modifizierte Buchstaben, Digraphen, besondere Abkürzungen und so weiter, wie oben erwähnt unter Alphabetischer Reihenfolgeund im Detail in der Alphabetischer Reihenfolge Artikel. Solche Algorithmen sind möglicherweise recht komplex und erfordern möglicherweise mehrere Durchgänge durch den Text.[1]

Die Probleme sind dennoch immer noch üblich, wenn der Algorithmus mehr als eine Sprache umfassen muss. Zum Beispiel in Deutsch Wörterbücher das Wort Ökonomisch kommt dazwischen Offenbar und Olfaktorisch, während Türkisch Wörterbücher behandeln o und ö als verschiedene Buchstaben, platzieren Oyun Vor Öbür.

Ein Standardalgorithmus zur Sammlung einer Sammlung von Zeichenfolgen, die aus Standards bestehen Unicode Symbole sind die UNICODE COLLATION ALGORITHM. Dies kann angepasst werden, um die entsprechende Kollationssequenz für eine bestimmte Sprache zu verwenden, indem die Standard -Collation -Tabelle angepasst wird. Mehrere solcher Schneiderungen werden in gesammelt Gemeinsames Gebietsschema -Datenrepository.

Tasten sortieren

In einigen Anwendungen können die Zeichenfolgen, an denen Elemente zusammengestellt werden, von den angezeigten Kennungen abweichen. Zum Beispiel, Das Leuchten könnte sein sortiert wie Leuchtend, die (sehen Alphabetischer Reihenfolge oben), aber es kann immer noch erwünscht werden, es als anzeigen als Das Leuchten. In diesem Fall können zwei Saiten Saiten gespeichert werden, einer für Anzeigzwecke und ein anderer für Kollationszwecke. Auf diese Weise für die Zusammenstellung verwendete Saiten werden genannt Tasten sortieren.

Probleme mit Zahlen

Manchmal ist es erwünscht, Text mit eingebetteten Zahlen unter Verwendung der richtigen numerischen Reihenfolge zu bestellen. Zum Beispiel geht "Abbildung 7b" vor "Abbildung 11a", obwohl '7' nach '1' in kommt Unicode. Dies kann auf erweitert werden römische Zahlen. Dieses Verhalten ist nicht besonders schwer zu produzieren, solange nur Ganzzahlen sortiert werden sollen, obwohl es die Sortierung erheblich verlangsamen kann. Zum Beispiel, Microsoft Windows tust das beim Sortieren Dateinamen.

Das richtige Sortieren der Dezimalstellen ist etwas schwieriger, da verschiedene Orte unterschiedliche Symbole für a verwenden Kommaund manchmal der gleiche Charakter wie a Komma wird auch als Trennzeichen verwendet, zum Beispiel "Abschnitt 3.2.5". Es gibt keine universelle Antwort darauf, wie solche Saiten sortiert werden können; Alle Regeln sind anwendungsabhängig.

Kennzeichnung der geordneten Elemente

In einigen Kontexten werden Nummern und Buchstaben nicht nur als Grundlage für die Festlegung einer Bestellung verwendet, sondern als Mittel zur Kennzeichnung von Elementen, die bereits bestellt wurden. Zum Beispiel werden Seiten, Abschnitte, Kapitel und dergleichen sowie die Elemente der Listen häufig auf diese Weise "nummeriert". Etikettierungsreihen, die verwendet werden können, umfassen gewöhnlich arabische Ziffern (1, 2, 3, ...), römische Zahlen (I, ii, iii, ... oder i, ii, iii, ...) oder Briefe (a, b, c, ... oder a, b, c, ...). (Eine alternative Methode zur Anzeige von Listenelementen, ohne sie zu nummerieren, besteht darin, a zu verwenden Kugelliste.))

Wenn für diesen Zweck Buchstaben eines Alphabets verwendet werden AufzählungEs gibt bestimmte sprachspezifische Konventionen, welche Buchstaben verwendet werden. Zum Beispiel die Russisch Briefe Ъ und Ь (schriftlich werden nur zur Änderung des vorhergehenden verwendet Konsonant) und normalerweise auch Ы, Й, und Ё, werden weggelassen. Auch in vielen Sprachen, die erweitert werden Lateinisches Skript, das Modifizierte Buchstaben werden oft nicht in der Aufzählung verwendet.

Siehe auch

Anmerkungen

  1. ^ Historisch gesehen handhabten Computer nur Text in Großbuchstaben (dies stammt aus Telegraph Konventionen).

Verweise

  1. ^ a b M Programmierung: Ein umfassender Leitfaden, Richard F. Walters, Digital Press, 1997

Externe Links