Hallo,
ich fange momentan an ein Programm zu schreiben, dass das Analysieren langer Zeichenketten ermöglichen soll (Spezieller Hauptzweck: Anzahl an identischen Substrings zählen). Dabei überschreitet die Länge der Zeichenkette fast immer die 10.000, die Maximallänge sollte aber im Optimalfall nach oben hin offen sein.
Jetzt frage ich mich was wohl der beste Weg ist so lange Zeichenketten zu behandeln:
[ol]
[li]Zeichenkette aus einer Datei in einen einzigen langen String einlesen (dann landet alles im Arbeitsspeicher)[/li][li]Mehrerer kleiner Strings nutzen und wenn die Randstellen untersucht werden diese (teilweise) zusammengefügt[/li][li]Ein ‘RandomAccesFile’ benutzen (wobei ich bisher noch nie damit gearbeitet habe)[/li][li]Etwas anderes woran ich noch gar nicht gedacht habe[/li][/ol]
Ich muss dabei in der Lage sein Substrings zu erstellen und zu untersuchen wie oft dieser Substring insgesamt vorkommt.
Wenn man nur einen einzige String hat könnte man über die “substring” und die “indexOf” Methoden machen, wobei ich mir nicht sicher bin ob das Einsetzen von “indexOf” die effektivste Methode wäre. Allerdings wäre es erst mal wichtig zu wissen wie ich solche großen Zeichenkette überhaupt sinnvoll behandeln kann. Vielleicht hat ja einer von euch schon Erfahrung damit.
etwas zu untersuchen mit indexOf geht im String ganz gut, was meinst du aber mit subString,
nur ab und zu mal vorne zigtausend wegschneiden und wegschmeißen damit hinten mehr ran kann?
dann wäre das auch unproblematisch,
falls du aber ständig jeden gefundenen Teilstring herausschneiden willst und das häufig vorkommt ist mehr zu überlegen,
du weißt dass man indexOf auch eine Startposition geben kann für neues Suchen hinter einem Vorkommen im gleichen String?
wenn du große Strings einlesen kannst, dann sieht es bisher danach aus als ginge String,
die Alternative ist StringBuilder, dann macht es auch nicht viel aus, 100x Strings der Länge 100 zusammenzufügen,
mit String + String in einer Schleife weniger zu empfehlen…, das ist eines der wenige Dinge auf die aufzupassen
(genau wie ständig substring zu rechnen, 1x je 10.000 Zeichen fällt nicht auf, 100x wäre schlimmer)
wenn es dir rein nach Performance geht, dann mag char[] in allen Schritten die bessere Variante sein,
kleine bis mittelgroße char[] einlesen, in einem größeren zusammensammeln und suchen usw.,
aber vielleicht nur kleiner Sprung gegenüber ganz anderem Programmaufbau dann
Von oben auf das Problem geschaut gibt es den einfachsten Fall, indem man die Maske des Suchstrings immer Stück für Stück weiterschiebt. Laufzeit O(m*n), mit m = Maskenlänge und n = Textlänge. Glaube ich in der Theorie kaum verbesserbar außer das man je nach Suchmaske und Fundstelle mehr als 1 Stelle weiterspringen kann. Weitere Möglichkeiten wäre das ganze durch Multithreading zu beschleunigen. Sollte wahrscheinlich mehr bewirken als alles andere.
Was anderes wäre es, wenn der Text N immer gleich bleibt und sich nur die Suchmaske M ändert. Aber das ist hier wahrscheinlich nicht der Fall.
Heißt das, daß die Zeichenkette größer als der Hauptspeicher werden kann? Falls ja, dann müsste man wohl mal bei den Bioinformatikern nach Lösungen wildern; ansonsten würde ich sie einfach in ein char-array einlesen. So lange der nötige Speicher vorhanden ist muss man ihn ja nicht brach liegen lassen.
Nicht wirklich. Allerdings hatte ich mich vor langer Zeit mal mit der Burrows Wheeler Transformation auseinandergesetzt. Dabei besteht ein Schritt darin, die Suffixe eines Strings zu sortieren (was die Suche nach identischen Substrings vereinfachen würde). Dafür gab es eine Menge pfiffige Algorithmen.
10.000 Zeichen sind aber noch keine Größenordnung, die einen PC irgendwie ins Schwitzen bringen dürften…
10.000, 100.000 oder auch 1.000.000 Zeichen sind noch nicht “viel”. Der Aufwand, die Daten auf der Festplatte zu lassen, würde sich wohl nicht lohnen. Wenn man sich in Größenordnungen von 100MB und mehr bewegt, kann es ggf. irgendwann sinnvoll sein, die Daten nicht komplett in den Speicher zu laden.
Zum Thema Pattern-Matching fiel mir noch der Boyer-Moore-Algorithmus ein. Ggf. kann man bei so langen Strings die Laufzeit damit unter O(n * m) drücken (falls das überhaupt relevant sein sollte).
Ich hab mal mit GB an Texten experimentiert (Zeitungsarchive) und die Ähnlichkeit von einzelnen Artikeln berechnet. Dazu wurden die Texte in Worte aufgesplittet und nur noch jedes Wort einzeln gespeichert. Jedes Wort erhält einen Index und ein Text wird dann auf die Indizes reduziert. Aus “Dies sind komplizierteste Anspielungen” wird dann z.B. “23 4997 1666 6732”
Die Anzahl der Worte in Beziehung zu den Texten ist dann logarithmisch. Bei neuen Texten kommen fast kaum noch neue Worte hinzu. Aber kommt alles auf den Anwendungsfall an.
Mir fallen da noch ein paar fragen ein, die die Auswahl der Methode beeinflussen:
[ul]
[li]Ist der Suchstring fester Text oder ein Muster mit “Wildcards”?
[/li][li]Handelt es sich mei dem zu durchsuchenden String und ein Text-Dokument, in dem ggf auch am Zeilenende getrennte Wörter vor kommen können oder ist das ein technischer Text ohne lexikalische Worttrennungen?
[/li][/ul]
bye
TT
Recht wenige Infos. Aber es stimmt schon: 100.000.000 Zeichen? OMG, das sind ja 200 MB!!! (-> Peanuts ;-)). Tendenziell würde ich da statt String eher StringBuilder (bzw. wenn möglich nur CharSequence) verwenden, weil der eine “rohere” Sicht auf den char[] liefert (ohne Pooling, unerwünschte Kopien etc).
Also substring sollte man vermeiden, weil kopiert und ein neues Objekt erstellt werden muss, das kostet - indexOf ist hingegen sehr effizient, weil ja kein regulärer Ausdruck verwendet wird.
Ein char ([]) hat auch 16 Bit, eventuell daran danken, wenn wirklich viele Daten verarbeitet werden sollen.
Gesucht ist aaa, dann beginnst du vorne und innerhalb der inneren Schleife von 0 bis 2, dann mit dem Zeichen weitermachen, das kein a gewesen ist. -
Kann sich denn die gesuchte Teil-Zeichenkette (nach der/durch die zu durchsuchenden Zeichenkette) ändern? Kann sie dann wieder die bereits durchsuchte Teil-Zeichenkette (den Anfang) “umfassen”?
Naja, wenn er größer als der Hauptspeicher wird, wäre das schon problematisch ;). Je nach Hardware könnte es aber theoretisch vorkommen, allerdings reicht es mir, wenn ich Daten im Rahmen des Hauptspeicher verarbeiten kann.
10.000 Zeichen sind eher als Mindestanforderung zu verstehen, ich würde mein Programm aber gerne so umsetzen, dass es bis ~2GB Daten keine Probleme gibt. (Auch wenn es wohl etwas länger dauern wird bis alles untersucht ist)
Der Text der durchsucht wird ist fest, der Text nachdem gesucht wird ändert sich aber öfters.
Genauer suche ich in dem Text nach sich besonders oft wiederholenden Teiltexten.
Es ist ein reicn technischer Text mit nur 4 verschiedenen möglichen Zeichen und ohne Leerstellen oder Zeilenumbrüche.
Der Algorithmus klingt zwar ganz interessant aber er ist, soweit ich das verstanden habe, eher dann effektiv wenn es viele verschiedene Buchstaben gibt, in meinem Text gibt es nur 4 Verschiedene.
Welchen Such-Algorithmus nutzt denn die JavaSE-Funktion „indexOf“ in String und StringBuilder. Das wäre eigentlich auch ganz interessant zu wissen, je nachdem kann ich dann schauen ob ich den verwende oder einen Anderen, der für meine Fall mit limitierter Buchstabenanzahl besser läuft.
Wenn ich am Ende mich für eine Implementierung entscheide in der ich „indexOf“ brauche wird mir „CharSequence“ wohl nicht genügen, aber StringBuilder besitzt diese Funktion. Macht es tatsächlich einen performancetechnischen Unterschied ob ich String oder StringBuilder nutze um meinen Text zu repräsentieren. Rein von den Klassennamen, hätte ich eher darauf getippt, dass String dafür besser geeignet ist als StringBuilder, da diese Klasse ja hauptsächlich den Zweck zu erfüllen scheint einen String zu erzeugen.
Stimmt schon, allerdings hatte ich als ich den Thread erstellt hatte gar nicht mehr daran gedacht, dass der Zweck des Programms eine große Bedeutung haben könnte, da ich mich voll auf die Darstellung großer Strings im Allgemeinen konzentriert hatte.
Rückblickend war das ziemlich kurzsichtig, aber jetzt habe ich ja ein paar Infos nachgereicht, hier noch mal kurz zusammengefasst:
[ul]
[li]Rein technischer Text ohne Worttrennnung, Zeilenumbrüche, o.ä.
[/li][li]Es gibt nur 4 verschiedene Buchstaben
[/li][li]min. 10.000 Zeichen lang, angestrebte verrechenbare Datenmenge: um die 2GB
[/li][li]Es wird nach sich besonders häufig wiederholenden Substrings gesucht (in der einfachsten Implementierung die mir gerade einfällt wäre die Rechenzeit quadratisch zur Datenmenge)
[/li][/ul]
So, schon mal Danke für die bisherigen Denkanstöße
MfG,
~Oneric
Hm, nach der (also deiner) Beschreibung hätte ich jetzt an die ersten 5 Buchstaben gedacht.
Mache das so, in Hauptspeicher (String, SB, CS, char[], erst mal wurscht), whitespaces erkennen, toLowerCase(), “substring(0, 5)” (also nicht wirklich, ist eigentlich effizient nicht), in eine Map, Häufigkeiten zählen, sortieren, Rückschlüsse erkennen, …
Wie gesagt, String erfährt intern eine „besonderere“ Behandlung, durch pooling & Co. (In einer der letzten Java-Versionen wurde da auch einiges geändert: substring auf String hatte eine Referenz des Originalstrings behalten, inzwischen macht es AFAIK eine Kopie, damit der GC den Rest wegräumen kann). Ansonsten… Namen sind Schall und Rauch, „StringBuilder“ und „StringBuffer“ unterscheiden sich z.B. nur in der synchronisation, d.h. man sollte da nicht zuuu viel reininterpretieren. Aber wenn man ohnehin schon einen String hat, und nur lesend drauf rumhantieren will, tut’s auch String.
Aaaaaber mit den zusätzlichen Informationen…
… geheimnisvoll mit den Händen wedel: Sind diese 4 Buchstaben angestrengt-nachdenklich an die Decke starr vielleicht zufällig…
A
G
C
uuuund
S?
Nein!
T!
???
Dafür sollte man auch mal byte in Betracht ziehen. Wie CyborgBeta schon gesagt hat: Ein char hat 16bit=2bytes, und ein byte nur 8 bit (also… 1 byte… ja…). Und wenn du von „2GB“ redest, kannst du entweder 1 Millarde Zeichen oder 2 Milliarden Zeichen meinen, wobei der Unterschied zwischen byte und char da dann eben 1GB bzw. 2GB ausmacht (von der Performance mal ganz abgesehen).
Natürlich wäre auf einem byte-Array sowas praktisches wie „indexOf“ oder „substring“ nicht vorhanden, aber das sind Sachen, die man als Dreizeiler nachbauen könnte.
(Nebenbei: Theoretisch könnte man diese 4 Zeichen auch in 2 bits pressen - und theoretisch könnte das für manche Dinge sinnvoll sein - aber bestimmte Dinge werden damit natürlich deutlich aufwändiger, wie etwa „indexOf“ usw).
Na super. Es geht um DNA/S. Da bin ich raus. .substring() und String ist dafür nicht geeignet. Wie Marco schon geschrieben hat, brauch man nur 00, 01, 10 und 11 - und dann wiederholt sich der Krams whrs. ewig, die Länge ist ja schon fast für die Festplatte zu viel.
Das geht doch schon in den Bereich quaternär(er) “Speicher” und Prozessor.
Ja, die Rechenzeit fängt bei >= (oder <= ? ) quadratisch an, das ist richtig. n^3 ist ja auch quadratisch. n!*n² wäre ja factorial time.
Edit: Hab nachgeguckt, n^3 ist eine eigene Bereich. Es ist schon spät, viell. fällt mir morgen etwas dazu ein. Noch gute Nacht.
[QUOTE=Oneric]Der Text der durchsucht wird ist fest, der Text nachdem gesucht wird ändert sich aber öfters.
Genauer suche ich in dem Text nach sich besonders oft wiederholenden Teiltexten.[/QUOTE]
Also sowas wie ein Substring-Histogramm? Da bietet es sich ja, wie schon erwähnt, an, ersteinmal eine Datenstruktur zu schaffen, die einem einfachen Zugang zu den relevanten Daten ermöglicht. Such mal nach suffix sorting und longest common prefix, da solltest du eine Menge brauchbare Algos finden (auch für die Verwendung mit externem Speicher). Da könnte man sich 2-4 der Algorithmen heraussuchen und implementieren; die Anwendung kann dann, je nach aktuellen Constraints, den passenden Algo auswählen.
In Prinzip schon, aber wenn du mehrere Symbole zu einem Byte/Short/Int zusammenfasst, dann hast du ja ein größeres Alphabet (und einen kürzeren String).
Das hängt vermutlich von der Implementierung ab. So wie es hiernachaussieht verwendet z.B. OpenJDK eine ganz banale lineare Suche.
Wenn das Programm nicht nur für mich privat sein soll, dann würde ich mit den Stringfunktionen von Java aber ehrlich gesagt gar nicht an das Problem herangehen wollen. Auch wenn es bequem aussieht und für 10.000 Zeichen noch gut funktioniert.
OT: Bei der BW hiess es immer: „Mach das ordentlich! Sonst machst du’s nochmal!“. Das war zwar damals zwar eher als Drohung denn als Prophezeiung gemeint, aber dennoch bewährt sich die Einhaltung diese „Weisheit“ immer und immer wieder…
[quote=Oneric]Rückblickend war das ziemlich kurzsichtig, aber jetzt habe ich ja ein paar Infos nachgereicht, hier noch mal kurz zusammengefasst:
Rein technischer Text ohne Worttrennnung, Zeilenumbrüche, o.ä.
Es gibt nur 4 verschiedene Buchstaben
min. 10.000 Zeichen lang, angestrebte verrechenbare Datenmenge: um die 2GB
Es wird nach sich besonders häufig wiederholenden Substrings gesucht (in der einfachsten Implementierung die mir gerade einfällt wäre die Rechenzeit quadratisch zur Datenmenge)[/quote]
Witzig, dass du immer noch nicht erwähnst, dass es um die 4 Basenpaare geht und du einen DNA-Strang statistisch bearbeiten willst.
Ich würde eher dazu raten, bereits existierende Software zu verwenden: Moara project (oder andere, gibt bestimmt einen Haufen Zeugs aus der Bioinformatik)
Das andere ist, dass du einfach immer noch nicht klar sagen kannst, ob
Deine Suchpatterns VOR der Suche feststehen und du dann deren Häufigkeit vergleichen willst
Du ohne Suchpatterns startest und während der Suche nach Mustern und Häufigkeiten suchst (eine oder zwei Größenordnungen schwieriger)
Es wird nach sich besonders häufig wiederholenden Substrings gesucht
Also nochmal die Frage: sind diese Substrings VOR der Suche bereits fixiert? Auch wenn man bei verschiedenen Durchläufen verschiedene Suchstrings verwendet ist das tatsächlich kein Problem, weil man nur “vorwärts” sucht.
Dazu kommen allerlei Probleme, etwa wenn ein Substring im anderen enthalten ist (du suchst nach abc und xyzabcvw) usw usf.
import java.util.Arrays;
import java.util.Comparator;```
``` public static int[][] finde(char[][] toFinde, char[] seq) {
ArrayList<int[]> res = new ArrayList<>();
for (int i = 0; i < seq.length; i++) {
a:
for (int j = 0; j < toFinde.length; j++) {
char[] toFinde1 = toFinde[j];
if (toFinde1.length > seq.length - i) {
break;
}
for (int k = 0; k < toFinde1.length; k++) {
if (toFinde1[k] != seq[i + k]) {
continue a;
}
}
res.add(new int[]{j, i, toFinde1.length}); // idx, start, len
}
}
int[][] res1 = new int[res.size()][];
for (int i = 0; i < res1.length; i++) {
res1** = res.get(i);
}
Arrays.sort(res1, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.valueOf(o1[1]).compareTo(o2[1]); // start
}
});
return res1;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
System.out.println(
Arrays.deepToString(
finde(new char[][]{
"bc".toCharArray(),
{'f', 'g'},
"bc".toCharArray() },
"abcdefghijkl".toCharArray()
)));
}```
[0, 1, 2],
[2, 1, 2],
[1, 5, 2],
In abcdefghijkl wird bc, fg, und bc gesucht.
Verbessern: Es wird char (16 Bit) verwendet. Die Methode ist lang, die Methode braucht Kommentare, und die Methode ist eigentlich schon sortiert. `break` anstatt `continue`
Also so hätte ich es gemacht, wenn es mehrere Teilzeichenketten gibt, und Speicher und so wichtig ist.
Darf sich der zu durchsuchende Teilzeichenkette ändern? Wenn ja, dann ist es whrs. auch nicht mehr n * m * m (^3).
So eine Methode ist eigtl schrecklich, aber es kann hier und da noch verbessert werden.
*** Edit ***
Ähm, sry, _die_ zu suchende Teilzeichenkette, also das, wonach gesucht werden soll, ... Wird diese vor, nach, während der Suche verändert? Wenn ja, dann kann nicht einfach durch Zeichen 1 bis n _iteriert_ werden, evtl. vor und zurück usw.
[quote=Marco13](Nebenbei: Theoretisch könnte man diese 4 Zeichen auch in 2 bits pressen - und theoretisch könnte das für manche Dinge sinnvoll sein - aber bestimmte Dinge werden damit natürlich deutlich aufwändiger, wie etwa „indexOf“ usw).
Das könnte durchaus nützlich sein um den Speicher zu schonen. indexOf und substring dürften sich aber mit Bit-Verschiebungen nachbauen lassen. Man muss nur daran denken, dass am Ende ein paar unbenutze Bits hängen könnten, wenn das letzte byte nicht voll ausgenutzt wird. Gegebenenfalls könnte dies die Ergebnisse verfälschen, wenn man nicht darauf achtet.
Also mal Klartext: BLAST, FASTA oder was anderes?[/quote]
BLAST und FASTA vergleichen, glaube ich, 2 DNS/A-Stränge (oder allgemeinere Amino/Basen-Folgen). Ich will dagegen nur einen einzelnen auf besonders häufig auftretende Basen-Folgen untersuchen.
So große DNS/A-Stränge will ich dann doch nicht unbedingt untersuchen.
Ich hatte zwar bisher leider nicht die Zeit mir das suffix-sorting mal genauer anzusehen, aber dass werde ich auf jeden Fall noch machen, schon mal Danke für den Hinweis.
Wenn ich 4(Byte) einzelne Buchstaben in einen zusammenfasse, und diesen dann auch als einen Buchstaben nehandele, könnte ich doch nur nach Basen-Folgen suchen, deren Länge ein Vielfaches von 4 ist, oder ?
[quote=Bleiglanz;112578]1. Deine Suchpatterns VOR der Suche feststehen und du dann deren Häufigkeit vergleichen willst
Du ohne Suchpatterns startest und während der Suche nach Mustern und Häufigkeiten suchst (eine oder zwei Größenordnungen schwieriger)
Es wird nach sich besonders häufig wiederholenden Substrings gesucht
Also nochmal die Frage: sind diese Substrings VOR der Suche bereits fixiert? Auch wenn man bei verschiedenen Durchläufen verschiedene Suchstrings verwendet ist das tatsächlich kein Problem, weil man nur „vorwärts“ sucht.[/quote]
Mir fiele momentan nur eine Implementierung ein, in der in einem einzelnen Suchdurchlauf der Suchstring konstant bleibt. Vielleicht ändert sich das aber noch wenn ich mir das suffix-sorting mal genauer angesehen habe.
Das ließe sich ganz einfach beheben, wenn ich fertig gesucht habe und die sich wiederholenden Basen-Folgen inklusive ihrer Häufigkeit in irgendeiner Liste hinterlegt habe, gehe ich einfach noch einmal durch diese Liste und sortiere alle Ergebnisse deren String ein Substring eines Anderen, mit der gleichen Häufigkeit, ist aus.
Also, unabhängig vom letztlich verwendeten Such-Algorithmus, würde ich sagen, dass sich
[ul]
[li]ein RandomAccesFile, für besonders große Texte lohnt, die das LImit des Hauptspeicher durchaus sprengen könnte, dafür muss man dann aber auf Parallelisierung o.ä. verzichten (wahrscheinlich langsamer)[/li][li]byte-Array mit komprimiereten Inhalt (1 byte = 4 Zeichen) wenn Parallelisierung möglich sein soll und die Datenmenge im Rahmen des Speichers bleibt, wenn man es besonders einfach haben will, kann man den Inhalt auch nicht komprimieren (1 byte = 1 Zeichen)[/li][/ul]
Wieder einmal Danke für die vielen Antworten und Hinweise
MfG,
~Oneric
Ok, meine Methode ist schrecklich, deshalb reiche ich hier mal was nach (verbesserter Aufruf):
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package pkg42textintext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
/**
* @author CB
*/
public class Main {
public static int[][] find(String... toFindAndSeq) {
if (toFindAndSeq == null || toFindAndSeq.length < 2) {
throw new IllegalArgumentException("toFindAndSeq == null || toFindAndSeq.length < 2");
}
char[][] toFind = new char[toFindAndSeq.length - 1][];
for (int i = 0; i < toFind.length; i++) {
toFind** = toFindAndSeq**.toCharArray();
}
char[] seq = toFindAndSeq[toFindAndSeq.length - 1].toCharArray();
return find1(toFind, seq);
}
public static int[][] find1(char[][] toFind, char[] seq) {
ArrayList<int[]> res = new ArrayList<>();
for (int i = 0; i < seq.length; i++) {
a:
for (int j = 0; j < toFind.length; j++) {
char[] toFinde1 = toFind[j];
if (toFinde1.length > seq.length - i) {
continue;
}
for (int k = 0; k < toFinde1.length; k++) {
if (toFinde1[k] != seq[i + k]) {
continue a;
}
}
res.add(new int[]{j, i, toFinde1.length}); // idx, start, len
}
}
int[][] res1 = new int[res.size()][];
for (int i = 0; i < res1.length; i++) {
res1** = res.get(i);
}
Arrays.sort(res1, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.valueOf(o1[1]).compareTo(o2[1]); // start
}
});
return res1;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
System.out.println(Arrays.deepToString(find("bc", "fg", "bc", "abcdefghijkl")));
}
}```
[[0, 1, 2], [2, 1, 2], [1, 5, 2]]
Speicherplatzverhalten: Mittelmäßig (16 Bit p Zeichen)
Laufzeitverhalten: Sehr gut
Korrekt"heit": Sehr gut
Bedienungskomfort: jetzt Sehr gut
Multithreading: Neee
flexible, zu suchende Teilzeichenketten: Neee
@Oneric : Wie gesagt, bioinformatik, aber unter n*m*k (n² bis n³) wird das nicht gehen, d. h., bei 4 Kernen würde / 4 den Blumenkohl auch nicht klein machen. Grüße, bis morgen.
Nein, wenn du sowieso auf Bitebene arbeitest, musst du das Suchpattern bitweise shiften und 4 Suchpatterns verwenden (jeweils um 2 Bit verschoben). Das Matching kannst du dann mit einer statischen Bitmaske, die du mit und verknüpfst und dann mit oder verknüpfen und die Gleichheit feststellen.
Beispiel:
Suchpattern 01
s = Zu durchsuchende Zeichenkette
p = Pattern
m = Maske
Vergleich ist dann immer s & m | p == p
p m
0100000000 11000000
0001000000 00110000
0000010000 00001100
...
