Repräsentative Zahl für einen String

Page 1 of 2 1 2
09/10/2010 20:06 .nAno#1
Heyho,
atm bastle ich nen wenig mit der Binären Zahlen Suche (->Link) rum.
Im Moment dachte ich mir es wäre ja ganz toll, auch Strings damit herauszufiltern und der einfachste Weg, der mir dazu einfällt wäre eine repräsentative Zahl für den Inhalt über die ASCII-Werte zu errechnen.

Nun ist meine Frage: wie soll ich das Anstellen?
Gefordert wäre a) eine niedrige bis keine Kollisionsrate und b) eine Zahl die sich im ähnlichen Bereich bewegt wie das eigentlich geforderte nur mit geringer Abweichung (z.B. wenn haha = 500 wäre, sollte hbhb = 505 sein), damit das nächste zutreffende Ergebnis gefunden werden könnte (ich hoffe ich konnte mich hier halbwegs verständlich ausdrücken).

Meine Ideen basieren alle auf einer erweiterten Quersumme, welche aber bei weitem nicht beide Kriterien erfüllen, ich hoffe irgendjemand kennt eine hübsche Lösung dafür bzw. kann mir helfen einen Eigenen Ansatz zu finden :)

Gruß nAno
09/10/2010 21:23 MrSm!th#2
Meinst du evtl Hashes?
Das wäre es denke ich mal; ein Wert, der (im Idealfall) eindeutig für einen Datensatz steht.
Problem wäre nur, dass man Hashes im Normal fall nicht rückgängig machen kann, also nicht auf die originalen Daten schließen kann.
Wäre das schlimm für deine Planung?
09/10/2010 21:34 Madd Eye#3
Code:
#include <iostream>
#include <string.h>

using namespace std;

int get_string_num(char eingabe[])
{
	int summe = 0;
	char * text = strtok(eingabe, "");

	for( int i = 0; i < sizeof( text ); i++ )
	{
		summe += int(text[i]);
	}

	return summe;
}

int main()
{
     char eingabe[256]
     while(1)
     {
       cin >> eingabe;
       int ausgabe = get_string_num(eingabe);
       cout << ausgabe << endl;
     }
  
     return 0;
}

Ne Sprache wär natürlich gut wenn du angeben würdest
Oben ist es in C++ gelöst

In VB.Net könnte es so aussehen:
Code:
    Private Function get_string_num(ByVal eingabe As String)
        Dim summe As Integer = 0
        Dim i As Integer = 0

        For i = 0 To eingabe.Length - 1

            summe += Asc(eingabe.Substring(i, 1))
        Next i

        Return summe
    End Function
@Mr. Sm!th

er sagte ja das er einen Repräsentativen Zahlen wert für einen String über die ASCII Werte errechnen möchte
So wie ich das verstanden hab darf sich dieser auch wiederholen
09/10/2010 23:08 MrSm!th#4
Er sollte doch möglichst keine Kollisionen bieten!
Also genau das, was man unter einem Hash versteht.
09/11/2010 00:48 .nAno#5
ja, ich dachte da an eine Art Hash (weswegen ich auch mal davon ausgegangen bin hier nicht unbedingt falsch zu sein ;)) Nur kenne ich keinen dessen Ausgabe rein auf Zahlen beschränkt ist und zusätzlich noch ne niedrige Kollisionsrate hat (um ehrlich zu sein nur meinen eigenen, der allerdings auch nur eine hohe Kollisionsanzahl aufweist; es mag auch daran liegen, dass mir md5 und Konsorten immer für meine Zwecke genügt haben)

Die Zahl muss nicht auf den Ursprung zurückzuführen sein, sie soll nur möglichst einen String beschrieben und nur diesen einen und dabei auf selbst geringe Abweichung im String mit einer äquivalenten Veränderung in der Zahl reagieren (ich wüsste nicht, wie ich es besser ausdrücken sollte, falls noch Verständnissprobleme bestehen sollten am besten einfach nochmal näher darauf eingehen ;))
09/11/2010 00:57 MoepMeep#6
Quote:
Originally Posted by Madd Eye View Post
Oben ist es in C++ gelöst
Ist es nicht. Das ist eher ein C/C++ mischmasch.
09/11/2010 01:05 Madd Eye#7
Nö ist C++ ^^

Hät aber noch nen Lösungsansatz
erzeug doch nen MD5 Hash und ersetz die Buchstaben mit dem ASCII Code
09/11/2010 01:11 MoepMeep#8
Quote:
Originally Posted by Madd Eye View Post
Nö ist C++ ^^
Für Mr.Copy&Paste schon, für jeden mit Ahnung, ist das kein reines c++ :>
09/11/2010 01:13 Cholik#9
Wieso nicht einfach std::binary_search() verwenden ==D

Naja eine repräsentative Zahl für einen String würde ja nur dann vielleicht Sinn machen wenn deine Strings zu lang wären, wieso nimmst du ansonsten nicht einfach die Strings wie sie sind?
Ansonsten weisst du ja denke ich schon wie die binäre Suche funktioniert, der Algorithmus ist ja nicht schwer zu verstehen für dich.
09/11/2010 02:26 .nAno#10
Quote:
Originally Posted by Madd Eye View Post
Nö ist C++ ^^

Hät aber noch nen Lösungsansatz
erzeug doch nen MD5 Hash und ersetz die Buchstaben mit dem ASCII Code
Das würde vermutlich Kollisionen verursachen und Kriterium b) wäre bestenfalls ab und an durch Zufall erfüllt, für eine gute Lösung wird man wahrscheinlich nicht bei den bisherigen Dingen bleiben können sondern muss sich etwas neues überlegen

Quote:
Originally Posted by Walter Sobchak View Post
Wieso nicht einfach std::binary_search() verwenden ==D

Naja eine repräsentative Zahl für einen String würde ja nur dann vielleicht Sinn machen wenn deine Strings zu lang wären, wieso nimmst du ansonsten nicht einfach die Strings wie sie sind?
Ansonsten weisst du ja denke ich schon wie die binäre Suche funktioniert, der Algorithmus ist ja nicht schwer zu verstehen für dich.
Den Algorithmus habe ich selber nach dem in Wikipedia genannten Funktionsprinzip geschrieben und nen wenig nach meinen Bedürfnissen modifiziert (die Grundform bleibt aber, obwohl der Algo selber hier gerade vollkommen uninteressant ist, es geht nur darum, das er lediglich Zahlen akzeptiert und diese auch wesentlich schneller verarbeitet werden können)

Falls es wem hilft die Problematik besser zu durchschauen, hier mal der relevante Source. Die genannte Modifikation besteht eigentlich nur darin, das er anstatt ein "Nein, hab nichts gefunden" die nächst größere Ziffer im Array (und gerade deswegen ist es mir so wichtig, dass die Strings sich je nach Inhalt ähneln oder unterscheiden, wenn es den gesuchten String nicht gibt soll der nächst bessere herangezogen werden) ausgibt:
PHP Code:
//C++ Code
int binarySearch(int *arr, int count, int desiredResult)
{
    int objCount = count;
    int middle = objCount / 2;


    //solange die Anzahl der infrage kommenden Objekte größer 1 ist UND das aktuell als Mitte gegebene Fach ungleich dem gesuchten Ergebeniss ist...
    while ( objCount > 1 && desiredResult != arr[middle] )
    {

        //...überprüfe, ob der Wert des mittleren Faches größer ist, als das gesuchte Ergebniss
        if( arr[middle] > desiredResult )
        {
            //Ja: setze das mittlere Fach auf die Mitte der Hälfte mit den ebenfalls größeren Werten
            middle *= 1.5;
        }
        //NEIN: Das Fach ist zwangsläufig kleiner, da diese Überprüfung erst gar nicht aufgerufen worden wäre, wenn der Wert des Mittlefaches mit dem Gesuchten übereinstimmen würde
        else
        {
            //also setze die Mitte auf den Mittelpunkt der Hälfte mit den kleineren Teilen
            middle *= 0.5;
        }

        // Die Anzahl der infrage kommenden Objekte im Array wurde halbiert, um das nächst präzisere Ergebniss zu erhalten, 
        //falls es keine exkate Übereinstimmung gibt, muss auch die Anzahl der potenziellen Ergebnisse halbiert werden
        objCount /= 2;
    }
    return arr[middle];
} 
09/12/2010 00:34 MrSm!th#11
Warum keinen Hash, der nur auf Zahlen basiert?
Soweit ich weiß, tut das jeder Hash, da das der Sinn eines Hashes ist.

MD5 zb. gibt einem auch ne Zahlenkette als Ergebnis.
Klar, wenn man die in einem String speichert, ist es meist als HEX Dezimale dargestellt, aber das heißt ja nix, ne Zahl ist es trotzdem und speichert man sie auch als diese, dann ist sie ganz normal in 1en und 0en gespeichert :p

Quote:
Die Zahl muss nicht auf den Ursprung zurückzuführen sein, sie soll nur möglichst einen String beschrieben und nur diesen einen und dabei auf selbst geringe Abweichung im String mit einer äquivalenten Veränderung in der Zahl reagieren (ich wüsste nicht, wie ich es besser ausdrücken sollte, falls noch Verständnissprobleme bestehen sollten am besten einfach nochmal näher darauf eingehen )
Dann ist ein Hash wie MD5 ja optimal.
09/12/2010 10:41 .nAno#12
Bestenfalls sollte die Zahl aber auf einen String zurückzuführen sein, da sie sonst nicht einzigartig ist, außerdem erfüllt MD5 nicht das 2. Kriterium. Ich hab nen wenig rumgespielt, von einer äquivalenten Veränderung kann nicht die Rede sein ;)
09/12/2010 12:00 MrSm!th#13
Oh entschuldige, Kriterium b habe ich überlesen.
Na dann passt ein Hash doch so überhaupt gar nicht, denn eines der Prinzipien eines Hashes ist, dass kleinste Änderungen an den Daten schon den ganzen Hash ändern.

Tja, aber deine Idee klingt für mich nicht so wirklich umsetzbar, da du damit automatisch auf die niedrige Kollisionsrate verzichten müsstest :/

Quote:
Bestenfalls sollte die Zahl aber auf einen String zurückzuführen sein, da sie sonst nicht einzigartig ist,
Versteh ich nicht, sagtest du nicht, man muss nicht auf den String zurückschließen können?
Und einzigartig ist ein Hash wohl, zumindest nahezu o.ô
Oder was meinst du nun damit?
09/12/2010 12:05 Shadow992#14
Das Problem liegt doch da:

Ein Hash muss immer eine gewisse Kollisionsrate haben, da es sonst kein Hash mehr wäre.
Könnte man jedem gehashten Wert einen String zuordnen, wäre es eine Verschlüsselung und kein Hash mehr.
Hashes kann man von daher ausschließen, wenn es wirklich extrem wichtig ist, dass jedem String genau eine Nummer zugewiesen werden darf.

Eine Verschlüsselung fällt wohl auch weg, da der String danach im besten Falle genau so lang wie vorher ist.

Mir persönlich würde jetzt nur eine Packer ähnliche Lösung einfallen.
So könnte man zum Beispiel aus dem hier:
Quote:
AAAABBBEFF
Das machen :
Quote:
A4B3EF2
Unser Code würde jetzt also alle hintereinander mehrfach auftauchende Buchstaben durch einen repräsentativen String ersetzen. A4 sagt uns dann zum Beispiel, dass an dieser Stelle 4 mal ein A kommt. Soetwas geht natürlich nicht immer gut und oft bringt es auch nicht gerade kürzere Wörter/Sätze.

Ich denke aber, dass du dich mehr in Richtung Packer bewegen solltest, da Verschlüsselungen und Hashes in diesem Fall wohl nicht das erwünschte Ergebniss liefern können.
09/12/2010 12:47 MrSm!th#15
Öhm...Der Idealhash hat eine Kollisionsrate von 0, das ist zwar nicht möglich, aber da es das Ideal ist, klingts für mich komisch, dass er eine haben muss.
Ich würde eher sagen, er kann nur eine Rate > 0 haben, da etwas anderes mit einem Hash nicht möglich ist.

Dein Vorschlag geht ja in Richtung Packen/Komprimieren, aber ich habe nicht verstanden, dass der String möglichst klein sein soll, sondern einfach, dass sein String durch eine Zahl dargestellt werden soll.
Und keine Angst, die Kollisionsrate bei guten Hashes ist so niedrig...da ist das egal, deshalb werden sie ja auch für Passwörter u.Ä. genommen.
Problem ist wie gesagt nur, dass es keine kleinen Abweichungen, bei kleinen Datenabweichungen gibt, sondern große.

Eine Idee wäre noch eine Checksum, allerdings wäre da die Kollisionsrate ziemlich groß.
Quote:
wenn haha = 500 wäre, sollte hbhb = 505
Das wäre dann eben damit möglich, nur wie gesagt, da wirst du eine sowas von große Kollisionsrate haben....
Ich denke mal, du musst dich für ein Kriterium entscheiden oder die Idee mit den Zahlen lassen ;<

Quote:
Hät aber noch nen Lösungsansatz
erzeug doch nen MD5 Hash und ersetz die Buchstaben mit dem ASCII Code
Ein Hash enthält keine Buchstaben.
Page 1 of 2 1 2