www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Search a file skiping whitespace

reply Willy Martinez <wmartinez thisisnotmyrealemail.com> writes:
Hello. I'm new to D but bear with me, please.

I have several files that look like this:

71104 08924 72394 13995 49707 98696
48245 08311 44066 67172 56025 07952
00384 37808 90166 13871 94258 37216

I'm trying to read those files and search for sequences of digits inside,
hopefully with the Boyer-Moore implementation in std.algorithm.

Right now I have made a small script that iterates over the .txt files in the
current directory and reads line by line and uses find on it.

But I haven't been able to write a range that removes the whitespace and can
be used with find. It should generate one long stream of digits like:

711040892472394139954970798696482450831144066671725602507952003843780890166138719425837216

Any help?

Thanks
Jul 16 2011
next sibling parent reply Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
On 7/16/2011 3:05 PM, Willy Martinez wrote:
 Any help?

import std.algorithm; import std.ascii; import std.stdio; void main(string[] argv) { auto s = "71104 08924 72394 13995 49707 98696 48245 08311 44066 67172 56025 07952 00384 37808 90166 13871 94258 37216"; auto t = filter!("!std.ascii.isWhite(a)")(s); bool found = canFind(t, "408"); writeln(t); writeln(found); } Outputs: 711040892472394139954970798696482450831144066671725602507952003843780890166138719425837216 true
Jul 16 2011
parent Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
On 7/16/2011 3:56 PM, Johann MacDonagh wrote:
 On 7/16/2011 3:05 PM, Willy Martinez wrote:
 Any help?

import std.algorithm; import std.ascii; import std.stdio; void main(string[] argv) { auto s = "71104 08924 72394 13995 49707 98696 48245 08311 44066 67172 56025 07952 00384 37808 90166 13871 94258 37216"; auto t = filter!("!std.ascii.isWhite(a)")(s); bool found = canFind(t, "408"); writeln(t); writeln(found); } Outputs: 711040892472394139954970798696482450831144066671725602507952003843780890166138719425837216 true

This is actually better: import std.algorithm; import std.ascii; import std.stdio; void main(string[] argv) { auto s = "71104 08924 72394 13995 49707 98696 48245 08311 44066 67172 56025 07952 00384 37808 90166 13871 94258 37216"; auto t = filter!( (c) { return isWhite(c); } )(s); bool found = canFind(t, "408"); writeln(t); writeln(found); } Otherwise we're relying on std.algorithm importing std.ascii.
Jul 16 2011
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 16.07.2011 23:05, Willy Martinez wrote:
 Hello. I'm new to D but bear with me, please.

 I have several files that look like this:

 71104 08924 72394 13995 49707 98696
 48245 08311 44066 67172 56025 07952
 00384 37808 90166 13871 94258 37216

 I'm trying to read those files and search for sequences of digits inside,
 hopefully with the Boyer-Moore implementation in std.algorithm.

 Right now I have made a small script that iterates over the .txt files in the
 current directory and reads line by line and uses find on it.

 But I haven't been able to write a range that removes the whitespace and can
 be used with find. It should generate one long stream of digits like:

 711040892472394139954970798696482450831144066671725602507952003843780890166138719425837216

If you wish to avoid storing all of this in an array by using e.g. filter _and_ use Boyer-Moore search on it then: No, you can't do that. The reason is that filter is ForwardRange with an important consequence that you can't look at arbitrary Nth element in O(1). And Boyer-Moore requires such and access to be anywhere efficient. Why doesn't filter not provide O(1) random access ? Because to get Nth element you'd need to check at least N (and potentially unlimited) number of elements before in case they get filtered out.
 Any help?

If I'd had this sort of problem I'd use something along the lines: auto file = File("yourfile"); foreach( line; file.ByLine) { auto onlyDigitis = array(filter!((x){ return !isWhite(x); })(line)); // this copies all digits to a new array auto result = find(onlyDigits, ... ); //your query here ///.... }
 Thanks

-- Dmitry Olshansky
Jul 16 2011
parent reply Willy Martinez <wmartinez thisisnotmyrealemail.com> writes:
== Quote from Dmitry Olshansky (dmitry.olsh gmail.com)'s article
 If you wish to avoid storing all of this in an array by using e.g.
 filter _and_  use Boyer-Moore search on it then: No, you can't do that.
 The reason is that filter is ForwardRange with an important consequence
 that you can't look at arbitrary Nth element in O(1). And Boyer-Moore
 requires such and access to be anywhere efficient.
 Why doesn't filter not provide O(1) random access ? Because to get Nth
 element you'd need to check at least N (and potentially unlimited)
 number of elements before in case they get filtered out.
 Any help?

auto file = File("yourfile"); foreach( line; file.ByLine) { auto onlyDigitis = array(filter!((x){ return !isWhite(x); })(line)); // this copies all digits to a new array auto result = find(onlyDigits, ... ); //your query here ///.... }
 Thanks


I don't mind storing it in memory. Each .txt file is around 20MB so the filtered string should be even smaller. Still, calling array gives this error: ..\..\src\phobos\std\algorithm.d(3252): Error: function std.algorithm.BoyerMooreFinder!(result,string).BoyerMooreFinder.beFound (string haystack) is not callable using argument types (dchar[]) ..\..\src\phobos\std\algorithm.d(3252): Error: cannot implicitly convert expression (haystack) of type dchar[] to string ..\..\src\phobos\std\algorithm.d(3252): Error: cannot implicitly convert expression (needle.beFound((__error))) of type string to dchar[] search_seq.d(13): Error: template instance std.algorithm.find!(dchar[],result,string) error instantiating From this code: import std.algorithm; import std.array; import std.file; import std.stdio; void main(string[] args) { auto needle = boyerMooreFinder(args[1]); foreach (string name; dirEntries(".", SpanMode.shallow)) { if (name[$-3 .. $] == "txt") { writeln(name); string text = readText(name); auto haystack = array(filter!("a >= '0' && a <= '9'")(text)); auto result = find(haystack, needle); writeln(result); } } } I'm using DMD 2.054 on Windows if that helps
Jul 16 2011
next sibling parent reply Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
On 7/16/2011 4:41 PM, Willy Martinez wrote:
 	auto needle = boyerMooreFinder(args[1]);

I'm confused. Boyer-Moore is when you want to find two or more elements efficiently in a range. When you create a BoyerMooreFinder you give it a range of elements it should search for. When you give it args[1] you are giving it a string which is immutable(char)[], or a range of characters. So if args[1] = "123" you're saying "search for 1, 2, or 3". Are you actually trying to search for multiple elements at the same time?
Jul 16 2011
parent Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
On 7/16/2011 4:43 PM, Johann MacDonagh wrote:
 On 7/16/2011 4:41 PM, Willy Martinez wrote:
 auto needle = boyerMooreFinder(args[1]);

I'm confused. Boyer-Moore is when you want to find two or more elements efficiently in a range. When you create a BoyerMooreFinder you give it a range of elements it should search for. When you give it args[1] you are giving it a string which is immutable(char)[], or a range of characters. So if args[1] = "123" you're saying "search for 1, 2, or 3". Are you actually trying to search for multiple elements at the same time?

Ugh, I'm dumb. I misread the documentation. Instead of defining "needle", just pass arg[1] into your call to find.
Jul 16 2011
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 17.07.2011 0:41, Willy Martinez wrote:
 == Quote from Dmitry Olshansky (dmitry.olsh gmail.com)'s article
 If you wish to avoid storing all of this in an array by using e.g.
 filter _and_  use Boyer-Moore search on it then: No, you can't do that.
 The reason is that filter is ForwardRange with an important consequence
 that you can't look at arbitrary Nth element in O(1). And Boyer-Moore
 requires such and access to be anywhere efficient.
 Why doesn't filter not provide O(1) random access ? Because to get Nth
 element you'd need to check at least N (and potentially unlimited)
 number of elements before in case they get filtered out.
 Any help?

auto file = File("yourfile"); foreach( line; file.ByLine) { auto onlyDigitis = array(filter!((x){ return !isWhite(x); })(line)); // this copies all digits to a new array auto result = find(onlyDigits, ... ); //your query here ///.... }
 Thanks


string should be even smaller. Still, calling array gives this error:

Not exactly calling array but I perfectly understand why you have confused it.
 ..\..\src\phobos\std\algorithm.d(3252): Error: function
 std.algorithm.BoyerMooreFinder!(result,string).BoyerMooreFinder.beFound (string
 haystack) is not callable using argument types (dchar[])
 ..\..\src\phobos\std\algorithm.d(3252): Error: cannot implicitly convert
 expression (haystack) of type dchar[] to string
 ..\..\src\phobos\std\algorithm.d(3252): Error: cannot implicitly convert
 expression (needle.beFound((__error))) of type string to dchar[]
search_seq.d(13):
 Error: template instance std.algorithm.find!(dchar[],result,string) error
 instantiating

Let's drill down to the problem through this barrage of crap: the problem statement is Error: cannot implicitly convert expression (haystack) of type dchar[] to string So (apparently) the problem is that after array(filter!(... you get array of dchars (unicode codepoints)as a result of filtering string (which is UTF-8 under the hood btw) while you are going to search an UTF-8 string. And UTF-8 string is (once again) is not random accessible in sense of codepoints (it's needs an UTF decode though it's clearly not needed in your case). The simplest workaround I can think of is convert needle to dstring: auto needle = boyerMooreFinder(to!dstring(args[1])); //found in std.conv
  From this code:

 import std.algorithm;
 import std.array;
 import std.file;
 import std.stdio;

 void main(string[] args) {
 	auto needle = boyerMooreFinder(args[1]);
 	foreach (string name; dirEntries(".", SpanMode.shallow)) {
 		if (name[$-3 .. $] == "txt") {
 			writeln(name);
 			string text = readText(name);
 			auto haystack = array(filter!("a>= '0'&&  a<= '9'")(text));
 			auto result = find(haystack, needle);
 			writeln(result);
 		}
 	}
 }


 I'm using DMD 2.054 on Windows if that helps

-- Dmitry Olshansky
Jul 16 2011
parent reply Johann MacDonagh <johann.macdonagh.no spam.gmail.com> writes:
On 7/16/2011 5:07 PM, Dmitry Olshansky wrote:
 Let's drill down to the problem through this barrage of crap:

 the problem statement is

 Error: cannot implicitly convert expression (haystack) of type dchar[]
 to string

 So (apparently) the problem is that after array(filter!(... you get
 array of dchars (unicode codepoints)as a result of filtering string
 (which is UTF-8 under the hood btw) while you are going to search an
 UTF-8 string.
 And UTF-8 string is (once again) is not random accessible in sense of
 codepoints (it's needs an UTF decode though it's clearly not needed in
 your case).
 The simplest workaround I can think of is convert needle to dstring:
 auto needle = boyerMooreFinder(to!dstring(args[1])); //found in std.conv

Nope, that doesn't work. Here's what he should do: import std.algorithm; import std.array; import std.file; import std.stdio; void main(string[] args) { foreach (string name; dirEntries(".", SpanMode.shallow)) { if (name[$-3 .. $] == "txt") { writeln(name); string text = readText(name); auto haystack = filter!("a >= '0' && a <='9'")(text); auto result = find(haystack, args[1]); writeln(result); } } } If you call array() on the filter you're already doing O(n) operations, meaning you're not going to get any performance benefit by being able to do Boyer-Moore. Correct me if I'm wrong, but I believe find() will do Boyer-Moore if it knows its haystack is random access. This is the power of templated programming. find! can generate an efficient find algorithm if it knows the range is random access, or default to a less efficient one if not.
Jul 16 2011
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 17.07.2011 1:28, Johann MacDonagh wrote:
 On 7/16/2011 5:07 PM, Dmitry Olshansky wrote:
 Let's drill down to the problem through this barrage of crap:

 the problem statement is

 Error: cannot implicitly convert expression (haystack) of type dchar[]
 to string

 So (apparently) the problem is that after array(filter!(... you get
 array of dchars (unicode codepoints)as a result of filtering string
 (which is UTF-8 under the hood btw) while you are going to search an
 UTF-8 string.
 And UTF-8 string is (once again) is not random accessible in sense of
 codepoints (it's needs an UTF decode though it's clearly not needed in
 your case).
 The simplest workaround I can think of is convert needle to dstring:
 auto needle = boyerMooreFinder(to!dstring(args[1])); //found in std.conv

Nope, that doesn't work. Here's what he should do: import std.algorithm; import std.array; import std.file; import std.stdio; void main(string[] args) { foreach (string name; dirEntries(".", SpanMode.shallow)) { if (name[$-3 .. $] == "txt") { writeln(name); string text = readText(name); auto haystack = filter!("a >= '0' && a <='9'")(text); auto result = find(haystack, args[1]); writeln(result); } } } If you call array() on the filter you're already doing O(n) operations, meaning you're not going to get any performance benefit by being able to do Boyer-Moore.

Actually with brute force you do O(mn) comparisons in general while there are Boyer-Moor implementations that will do O(n). Now with an alphabet of 0..9 I'd say you won't get a lot of speed up with Boyer-Moore, in any case I'd suggest OP to at least test both. In this case however my bet is on bruteforce (given an extra allocation on each string with B-M).
 Correct me if I'm wrong, but I believe find() will do Boyer-Moore if 
 it knows its haystack is random access. This is the power of templated 
 programming. find! can generate an efficient find algorithm if it 
 knows the range is random access, or default to a less efficient one 
 if not.

No, the problem of BoyerMoor search is there is some preparatory overhead to construct lookup table, apparently that table is stored in that BoyerMoorFinder. Frankly, std.algorithm might add at least one another sting searching algorithm e.g. http://monge.univ-mlv.fr/~lecroq/string/ -- Dmitry Olshansky
Jul 16 2011