String-Index rückwirkend bestimmen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 1:16 am

Hallo zusammen,

ich bin neu hier im Forum und benötige Hilfe bei einem Problem, dass mich schon seit einigen Wochen beschäftigt.
Ich habe unter Linux ein kleines Brute-Force Programm in C geschrieben. Es ist nichts besonderes und nur zur Übung.
Das Programm funktioniert auch soweit ganz gut. Vor ca. zwei Wochen kam ich dann auf die Idee, einen Zähler zu
implementieren. Also die Idee ist, dass jeder generierte String gezählt werden soll. So das am Ende, unabhängig davon
ob ein Treffer gelandet wurde oder nicht, angezeigt wird wie viele Strings erzeugt wurden.
Der Zähler ist eine ganz normale Integer-Variable die nach jedem generierten String inkrementiert wird.
Also

Code: Alles auswählen

Hier mal grob der Aufbau (!!!also nicht vollständig!!!)
/* Globale Variablen */
const char LiteralsLower[] = "abcdefghijklmnopqrstuvwxyz" //z.B. nur Kleinbuchstaben
int NLiterals = sizeof( LiteralsLower ) -1; // entspricht genau 26
int main()
{
    int Count; // Zähler
#pragma omp parallel default( none ) shared ( ... ) reduction( +: Count )
{
    ... Aufgaben ....
    #pragma omp for schedule( dynamic )
    for( ... )
    {
        ...Aufgaben ...
        BruteForceFunktion( ..., ..., &Count ) // Hier wird u.a. Count als Argument an einen Zeiger übergeben, der das Zählen innerhalb der BF()-Funktion übernimmt
    }
}
/* nach jedem generierten String innerhalb der BF()-Funktion */
++*CountPtr; // Zähler inkrementieren
(Ich hoffe ihr versteht was ich ungefähr meine.)

Code: Alles auswählen

Die Strings werden folgendermaßen generiert:
--------------------------------------------------------------
String    |     Index    |    Count
"a'"                  1             1
"b"                   2             2
"c"                   3             3
.
.
.
"z"                   26            26
"aa"                 27            27
"ab"                 28            28
.
usw.
Also im Grunde genommen eigentlich ganz einfach. :)
Nicht aber, wenn das Ganze parallelisiert abläuft. Den das Ganze geschieht innerhalb eines parallelisierten Blocks mittels OpenMP.
Am Ende stimmt die Zählung nur dann wenn eben kein Treffer gelandet wurde. Da somit der parallelisierte Block erst verlassen wird,
wenn die Arbeit bis zum Ende getan wurde. Bei einem Treffer springt man eben raus. Dadurch kann die Reduction nicht vollendet werden.
Habe wirklich tausend verschiedene Dinge ausprobiert. Mit mutexen oder mit omp atomic, flush usw. Sorry das ich das nicht so detailliert beschreibe.
Aber ich habe wirklich alles mögliche versucht und die Zählung funktioniert so einfach nicht. Eben weil bei einem Treffer die Arbeit innerhalb des
parallelisierten Bereichs nicht bis zur Vollendung läuft.

Daher meine Frage an euch, gibt es eine Möglichkeit, wenn der gesuchte String gefunden wurde, den Index rückwirkend zu bestimmen?
Nehmen wir mal "test" als Beispiel. Also "test" ist der zu suchende String. "test" hat z.B. den Index '355414'. So wie "a" den Index '1' hat,
"z" den Index '26' und "aa" den Index '27' usw. Klar, wenn man anstatt

Code: Alles auswählen

const char LiteralsLower[] = "abcdefghijklmnopqrstuvwxyz"
z.B. folgendes verwendet:

Code: Alles auswählen

const char LiteralsLowerDigits[] = "abcdefghijklmnopqrstuvwxyz0123456789"
ändert sich auch dementsprechend der Index.
Aber bleiben wir einfach mal bei LiteralsLower[] = "a...z" = 26.
Wäre es irgendwie möglich durch eine bestimmte Rechenformel den Index von "test" (355414) rückwirkend zu bestimmen? Z.B. anhand der String-Länge, NLiteralsLower = 26 usw.?

Ich hoffe ich konnte mein Anliegen relativ gut beschreiben. :)

Würde mich über Antworten sehr freuen.

Grüße
DaveX

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 2:48 am

DaveX hat geschrieben:Wäre es irgendwie möglich durch eine bestimmte Rechenformel den Index von "test" (355414) rückwirkend zu bestimmen? Z.B. anhand der String-Länge, NLiteralsLower = 26 usw.?
Ich würde behaupten ja.

----------------------------------------------------------------
Nehmen wir an du hast nur Kleinbuchstaben und dein Ergebnis ist "dabcd".
Um an der letzten Stelle zu 'd' zu kommen hast du 4 Schritte gebraucht ('a' -> 'b' -> 'c' -> 'd').

Um an der vorletzten Stelle zu 'c' zu kommen hast du 3 Schritte an der vorletzten Stelle gebraucht ('a' -> 'b' -> 'c'). Für alle außer den letzten Schritt (wo du dein Ergebnis gefunden hast) hast du für jeden der beiden Schritte an der vorletzten Stelle aber 26 Schritte für die letzte Stelle gebraucht.
Insgesamt sind das also für die letzten beiden Stellen (26 * 2) + 4 Schritte.

Um an der dritten Stelle zu 'b' zu kommen hast du 2 Schritte an der dritten Stelle gebraucht ('a' -> 'b'). Wieder lassen wir den letzten (unvollständigen) Schritt weg, du hast also 1 Schritt. In diesem Schritt hast du an den letzten beiden Stellen jeweils alle 26 Möglichkeiten durchprobiert, also 26 * 26
Insgesamt sind das also für die letzten 3 Stellen (26 * 26 * 1) + (26 * 2) + 4 Schritte.

Um an der zweiten Stelle zu 'a' zu kommen hast du 1 Schritt gebraucht ('a'). Dort hast du aber auch sofort dein Ergebnis gefunden, also hast du 0 mal alle 26 * 26 * 26 Möglichkeiten rechts davon durchprobiert.
Insgesamt sind das also für die letzten 4 Stellen (26 * 26 * 26 * 0) + (26 * 26 * 1) + (26 * 2) + 4 Schritte.

Nun zur letzten Stelle. Hier hast du (abzüglich dem letzten Schritt) 3 Schritte. Um zu dieser Stelle zu kommen, hast du also 3 mal die letzten 4 Stellen durchprobieren müssen, also 26 * 26 * 26 * 26 * 3.
Insgesamt kommst du also auf: (26 * 26 * 26 * 26 * 3) + (26 * 26 * 26 * 0) + (26 * 26 * 1) + (26 * 2) + 4 = 1 371 660

Man kann also folgende Formel aufstellen:
Summe[1 <= i <= n] (m^(n - i) * p(i))
Wobei:
n = Anzahl an Stellen
m = Anzahl an möglichen Zeichen
p(i) = Index des Zeichens am Index i im Charset, beginnend mit 0

Falls du deine Strings inkrementell bildest ("zzz" => "aaaa") kannst du die Möglichkeiten jeweils einfach mit n^m berechnen und dazu addieren.
----------------------------------------------------------------

Meinungen dazu?

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 3:40 am

Hallo dani93 :),

danke für die recht schnelle Antwort.
DaveX hat geschrieben:Wäre es irgendwie möglich durch eine bestimmte Rechenformel den Index von "test" (355414) rückwirkend zu bestimmen? Z.B. anhand der String-Länge, NLiteralsLower = 26 usw.?
Ich würde behaupten ja.[/quote]Das wäre toll. Denn dann könnte ich mir diese Zählerei innerhalb des parallelisierten Blocks sparen. Das hat nämlich leider nicht richtig funktioniert. Ich bin mittlerweile so davon genervt, dass ich eben nach einer Alternative suche. Durch deine Antwort hast du wirklich Hoffnungen in mir geweckt. :)
dani93 hat geschrieben:----------------------------------------------------------------
Nehmen wir an du hast nur Kleinbuchstaben und dein Ergebnis ist "dabcd".
Um an der letzten Stelle zu 'd' zu kommen hast du 4 Schritte gebraucht ('a' -> 'b' -> 'c' -> 'd').

Um an der vorletzten Stelle zu 'c' zu kommen hast du 3 Schritte an der vorletzten Stelle gebraucht ('a' -> 'b' -> 'c'). Für alle außer den letzten Schritt (wo du dein Ergebnis gefunden hast) hast du für jeden der beiden Schritte an der vorletzten Stelle aber 26 Schritte für die letzte Stelle gebraucht.
Insgesamt sind das also für die letzten beiden Stellen (26 * 2) + 4 Schritte.

Um an der dritten Stelle zu 'b' zu kommen hast du 2 Schritte an der dritten Stelle gebraucht ('a' -> 'b'). Wieder lassen wir den letzten (unvollständigen) Schritt weg, du hast also 1 Schritt. In diesem Schritt hast du an den letzten beiden Stellen jeweils alle 26 Möglichkeiten durchprobiert, also 26 * 26
Insgesamt sind das also für die letzten 3 Stellen (26 * 26 * 1) + (26 * 2) + 4 Schritte.

Um an der zweiten Stelle zu 'a' zu kommen hast du 1 Schritt gebraucht ('a'). Dort hast du aber auch sofort dein Ergebnis gefunden, also hast du 0 mal alle 26 * 26 * 26 Möglichkeiten rechts davon durchprobiert.
Insgesamt sind das also für die letzten 4 Stellen (26 * 26 * 26 * 0) + (26 * 26 * 1) + (26 * 2) + 4 Schritte.

Nun zur letzten Stelle. Hier hast du (abzüglich dem letzten Schritt) 3 Schritte. Um zu dieser Stelle zu kommen, hast du also 3 mal die letzten 4 Stellen durchprobieren müssen, also 26 * 26 * 26 * 26 * 3.
Insgesamt kommst du also auf: (26 * 26 * 26 * 26 * 3) + (26 * 26 * 26 * 0) + (26 * 26 * 1) + (26 * 2) + 4 = 1 371 660
Also damit ich dich richtig verstehe bzw. du mich :) :
Dein Beispiel mit "dabcd" entspricht in meinem Programm folgendem Index: 1 846 914. Wenn ich die Parallelisierung komplett auskommentiere, funktioniert ja die Zählung einwandfrei (doch leider nur seriell :( )
Die Count-Variable beginnt beim Zählen mit 1, d.h. "a" = 1, "b" = 2, "c" = 3 usw. Ich habe das so implementiert.
Ich möchte noch hinzufügen, dass mein Programm die Strings folgendermaßen generiert:

Code: Alles auswählen

"zz" -> "aaa" -> "aab" -> "aac" -> usw. -> "zzz" -> "aaaa" -> "aaab"
Deine Beschreibung oben, wie man das berechnet klingt genau nach dem was ich suche. :)
Würde das aber mit der Reihenfolge wie mein Programm die Strings erzeugt passen? Also ich frage nur deshalb, weil du mit deiner
Formel bei "dabcd" zu folgendem Ergebnis gekommen bist: 1 371 660. Bei mir aber 1 846 914 gezählt werden. Vielleicht bist du bei
deiner Formel von folgendem ausgegangen:

Code: Alles auswählen

"zz" -> "aaa" -> "baa" -> "caa" -> usw. -> "zzz" -> "aaaa" -> "baaa"
Verstehst du was ich meine?
dani93 hat geschrieben:Falls du deine Strings inkrementell bildest ("zzz" => "aaaa") kannst du die Möglichkeiten jeweils einfach mit n^m berechnen und dazu addieren.
----------------------------------------------------------------
Könntest du den letzten Satz etwas konkretisieren für mich? Ich habe das nicht ganz verstanden. Ansonsten klingt das genau nach dem was ich suche. :)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 3:58 am

DaveX hat geschrieben:
dani93 hat geschrieben:Falls du deine Strings inkrementell bildest ("zzz" => "aaaa") kannst du die Möglichkeiten jeweils einfach mit n^m berechnen und dazu addieren.
----------------------------------------------------------------
Könntest du den letzten Satz etwas konkretisieren für mich? Ich habe das nicht ganz verstanden. Ansonsten klingt das genau nach dem was ich suche. :)
Der Satz beschreibt genau das, was du darüber als Problem ansprichst ^^
Meine Berechnung gibt dir die Anzahl aller durchprobierten 5-stelligen Möglichkeiten zurück, also:

Code: Alles auswählen

aaaaa
aaaab
aaaac
...
dabcd
Was dabei fehlt sind alle Möglichkeiten mit weniger Stellen, also a-z, aa-zz, aaa-zzz und aaaa-zzzz. Du musst in diesen Fällen nichts beachten, du versuchst immer alle Kombinationen. Für eine Zahl mit n Stellen und m Zeichen sind das m^n Möglichkeiten (ich hab oben n^m geschrieben, es sollte aber m^n sein!).

Bei a-z:
n = 1
m = 26
m^n = 26

Bei aa-zz:
n = 2
m = 26
m^n = 676

usw.

Du nimmst also das Ergebnis von vorhin: 1371660
Und addierst die Anzahl für alle Möglichkeiten mit weniger Stellen hinzu, also:
1371660 + 26 + 676 + 17576 + 456976 = 1846914
Ta da ;)

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 4:23 am

Wow. :) Ich bin völlig beeindruckt. Auch wenn ich das noch nicht ganz nachvollziehen kann. Aber das ist es. Das ist die Lösung meines Problems der letzten Wochen. Jetzt muss ich mir das nur nochmal in aller Ruhe ansehen um das richtig nachvollziehen zu können. Jedenfalls vielen vielen Dank für's Erste. Ich werde, auch wenn ich es verstanden haben sollte, auf jeden Fall noch mal auf dich zurück kommen müssen. Vielleicht könntest du mir auch dabei helfen, dass Ganze programmiertechnisch umzusetzen. Vielen Dank dani93. Wirklich super. ;)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 12:13 pm

Was genau davon ist denn unklar?

Ich hab das Thema übrigens nach "Algorithmen und Konzepte" verschoben, das passt hier besser her.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 2:48 pm

Hallo dani93, keine Sorge. Du hast es wirklich super beschrieben. Daran lag es nicht. :) Letzte Nacht war ich schon extrem müde und dementsprechend blieb der AHA-Effekt aus.
Aber heute nach dem ich wieder ausgeschlafen bin, habe ich deine Formel endlich verstanden. Ich muss sagen, du bist ein richtiges Genie. ;)
Ich habe deine Formel auf "test" angewendet:

Code: Alles auswählen

"test"
(26*26*26*19)+(26*26*4)+(26*18)+20 = 337136

337136 + 26 + 676 + 17576 = 355414 <- absolut RICHTIG!
Echt super von dir und wirklich vielen vielen Dank. :)

Jetzt muss ich mir nur noch überlegen, wie ich das programmiertechnisch umsetzen kann.
Also nicht die Formel, sondern wie ich die benötigten Zahlen zum Rechnen aus dem String
bekomme. Du bist echt mein Held. :) Ich danke dir vielmals. ;)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 3:04 pm

DaveX hat geschrieben:Jetzt muss ich mir nur noch überlegen, wie ich das programmiertechnisch umsetzen kann.
Also nicht die Formel, sondern wie ich die benötigten Zahlen zum Rechnen aus dem String bekomme.
In C++ würde ich eine Map verwenden:
http://www.cplusplus.com/reference/map/map/

Falls du C programmierst und nicht grad auf jedes Byte optimierst, würde ich mir eine Map einfach nachbauen:

Code: Alles auswählen

#include <stdio.h>
#include <string.h>

const char literals[] = "abc123456789defghijklmnopqrstuvwxyz";

int main()
{
    int pos[256] = { 0 };
    for( unsigned int i = 0; i < strlen( literals ); i++ )
        pos[(int)literals[i]] = i;
    
    const char test[] = "dabcd";
    for( unsigned int i = 0; i < strlen( test ); i++)
        printf("%c %d\n", test[i], pos[(int)test[i]]);

    return 0;
}

Code: Alles auswählen

$ gcc -o pos pos.c -Wall -std=c99
$ ./pos 
d 12
a 0
b 1
c 2
d 12
Damit kommst du in konstanter Zeit auf den Index eines Zeichens im Charset. Das funktioniert für beliebige Zeichen und (eindeutige) Kombinationen im ASCII-Bereich, für andere Bereiche müsstest du das "pos"-Array einfach entsprechend vergrößern.

Die Gesamtlänge des Strings und des Charsets zu ermitteln ist mit strlen() einfach erledigt.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 3:27 pm

Ich bin absolut überwältigt. Ich weiß gar nicht mehr was ich noch sagen soll. Echt vielen vielen Dank. :)
Du hast mir wirklich sehr geholfen. Dafür bin ich dir unendlich dankbar. Ich werde dieses Forum weiter empfehlen wo
ich nur kann. Hier bekommt man mehr als 100% Hilfe. Absolut TOP!!! ;) :) :) :)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 3:33 pm

Bitte :)
Wenn du proggen.org unterstützen willst, bist du herzlich eingeladen dich neben dem Forum auch noch im Wiki auszutoben. Du könntest z.B. etwas über OpenMP schreiben.

Antworten