stil / dawgdic Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/dawgdic
License: BSD 3-Clause "New" or "Revised" License
Automatically exported from code.google.com/p/dawgdic
License: BSD 3-Clause "New" or "Revised" License
There doesn't seem to be a license file. Your GitHub settings and https://github.com/pytries/DAWG state that this is BSD, but I think a LICENSE
file would be great anyway.
Hello,
It seems there is no way to store binary data containing 0 bytes in DAWG, at
least it seems that Completer doesn't support it (completer.key() and
completer.length() returns values truncated at first 0 byte).
My use case is to store binary payload as a part of keys. The keys are
<utf8-encoded unicode key> + chr(255) + <binary_value>
this will allow implementing mapping from unicode to a list of possible binary
values using DAWG where values will be compressed just like keys; in order to
get all values Completer class may be used.
Zero bytes are not an issue for the utf8 keys because utf8 text is guaranteed
to not include them. chr(255) also can't be a part of utf8-encoded string so it
is fine as a separator. But zeroes in binary data renders this scheme
non-working.
Is there a workaround? Thanks.
Original issue reported on code.google.com by [email protected]
on 21 Aug 2012 at 10:19
dawgdic test suite is failing on big-endian machines:
no. keys: 14
no. states: 28
no. transitions: 40
no. merged states: 20
no. merging states: 3
no. merged transitions: 7
no. elements: 256
no. unused elements: 215 (83.9844%)
dictionary size: 1024
no. units: 256
guide size: 512
*** glibc detected *** ../src/dawgdic-find: free(): invalid next size (fast):
0x206817c8 ***
======= Backtrace: =========
/lib/powerpc-linux-gnu/libc.so.6(+0x84fc4)[0x1feebfc4]
/lib/powerpc-linux-gnu/libc.so.6(cfree+0x8c)[0x1fef159c]
/usr/lib/powerpc-linux-gnu/libstdc++.so.6(_ZdlPv+0x2c)[0x201c9a3c]
/usr/lib/powerpc-linux-gnu/libstdc++.so.6(_ZNSs4_Rep10_M_destroyERKSaIcE+0x24)[0
x201a6a30]
/usr/lib/powerpc-linux-gnu/libstdc++.so.6(+0xa8aa8)[0x201a6aa8]
/usr/lib/powerpc-linux-gnu/libstdc++.so.6(_ZNSs7reserveEj+0xdc)[0x201a81dc]
/usr/lib/powerpc-linux-gnu/libstdc++.so.6(_ZSt7getlineIcSt11char_traitsIcESaIcEE
RSt13basic_istreamIT_T0_ES7_RSbIS4_S5_T1_ES4_+0x248)[0x20169774]
../src/dawgdic-find(+0x16d4)[0x202346d4]
/lib/powerpc-linux-gnu/libc.so.6(+0x1f7ec)[0x1fe867ec]
/lib/powerpc-linux-gnu/libc.so.6(+0x1f9b0)[0x1fe869b0]
======= Memory map: ========
00100000-00103000 r-xp 00000000 00:00 0 [vdso]
1fe67000-1ffd3000 r-xp 00000000 fd:07 5272
/lib/powerpc-linux-gnu/libc-2.13.so
1ffd3000-1ffe3000 ---p 0016c000 fd:07 5272
/lib/powerpc-linux-gnu/libc-2.13.so
1ffe3000-1ffe7000 r--p 0016c000 fd:07 5272
/lib/powerpc-linux-gnu/libc-2.13.so
1ffe7000-1ffe8000 rw-p 00170000 fd:07 5272
/lib/powerpc-linux-gnu/libc-2.13.so
1ffe8000-1ffeb000 rw-p 00000000 00:00 0
1fffb000-20010000 r-xp 00000000 fd:07 1015
/lib/powerpc-linux-gnu/libgcc_s.so.1
20010000-2001f000 ---p 00015000 fd:07 1015
/lib/powerpc-linux-gnu/libgcc_s.so.1
2001f000-20020000 rw-p 00014000 fd:07 1015
/lib/powerpc-linux-gnu/libgcc_s.so.1
20030000-200da000 r-xp 00000000 fd:07 5285
/lib/powerpc-linux-gnu/libm-2.13.so
200da000-200ea000 ---p 000aa000 fd:07 5285
/lib/powerpc-linux-gnu/libm-2.13.so
200ea000-200ed000 r--p 000aa000 fd:07 5285
/lib/powerpc-linux-gnu/libm-2.13.so
200ed000-200ee000 rw-p 000ad000 fd:07 5285
/lib/powerpc-linux-gnu/libm-2.13.so
200fe000-20206000 r-xp 00000000 fd:07 5530
/usr/lib/powerpc-linux-gnu/libstdc++.so.6.0.16
20206000-20216000 ---p 00108000 fd:07 5530
/usr/lib/powerpc-linux-gnu/libstdc++.so.6.0.16
20216000-2021b000 r--p 00108000 fd:07 5530
/usr/lib/powerpc-linux-gnu/libstdc++.so.6.0.16
2021b000-2021d000 rw-p 0010d000 fd:07 5530
/usr/lib/powerpc-linux-gnu/libstdc++.so.6.0.16
2021d000-20223000 rw-p 00000000 00:00 0
20233000-20238000 r-xp 00000000 fd:02 1179764
/build/buildd-dawgdic_0.4.2-1-powerpc-JribeN/dawgdic-0.4.2/obj/src/dawgdic-find
20247000-20248000 r--p 00004000 fd:02 1179764
/build/buildd-dawgdic_0.4.2-1-powerpc-JribeN/dawgdic-0.4.2/obj/src/dawgdic-find
20248000-20249000 rw-p 00005000 fd:02 1179764
/build/buildd-dawgdic_0.4.2-1-powerpc-JribeN/dawgdic-0.4.2/obj/src/dawgdic-find
2067f000-206a0000 rwxp 00000000 00:00 0 [heap]
40000000-40020000 r-xp 00000000 fd:07 5277
/lib/powerpc-linux-gnu/ld-2.13.so
40020000-40021000 r--p 00020000 fd:07 5277
/lib/powerpc-linux-gnu/ld-2.13.so
40021000-40022000 rw-p 00021000 fd:07 5277
/lib/powerpc-linux-gnu/ld-2.13.so
40022000-40026000 rw-p 00000000 00:00 0
40027000-4002a000 rw-p 00000000 00:00 0
40100000-40121000 rw-p 00000000 00:00 0
40121000-40200000 ---p 00000000 00:00 0
ffcef000-ffd04000 rw-p 00000000 00:00 0 [stack]
Aborted
FAIL: guide-test.sh
Full build logs:
https://buildd.debian.org/status/fetch.php?pkg=dawgdic&arch=s390&ver=0.4.2-1&sta
mp=1332964908
https://buildd.debian.org/status/fetch.php?pkg=dawgdic&arch=s390x&ver=0.4.2-1&st
amp=1332966563
https://buildd.debian.org/status/fetch.php?pkg=dawgdic&arch=sparc&ver=0.4.2-1&st
amp=1332965723
https://buildd.debian.org/status/fetch.php?pkg=dawgdic&arch=mips&ver=0.4.2-1&sta
mp=1333231735
https://buildd.debian.org/status/fetch.php?pkg=dawgdic&arch=powerpc&ver=0.4.2-1&
stamp=1332965113
http://buildd.debian-ports.org/status/fetch.php?pkg=dawgdic&arch=ppc64&ver=0.4.2
-1&stamp=1333032316
The failing command is:
../src/dawgdic-find -g lexicon.dic < query
Backtrace:
#0 0x0fc6b98c in raise () from /lib/powerpc-linux-gnu/libc.so.6
#1 0x0fc71040 in abort () from /lib/powerpc-linux-gnu/libc.so.6
#2 0x0fcab87c in ?? () from /lib/powerpc-linux-gnu/libc.so.6
#3 0x0fcb8fc4 in ?? () from /lib/powerpc-linux-gnu/libc.so.6
#4 0x0fcbe59c in free () from /lib/powerpc-linux-gnu/libc.so.6
#5 0x0ff96a3c in operator delete(void*) () from
/usr/lib/powerpc-linux-gnu/libstdc++.so.6
#6 0x0ff73a30 in std::string::_Rep::_M_destroy(std::allocator<char> const&) ()
from /usr/lib/powerpc-linux-gnu/libstdc++.so.6
#7 0x0ff73aa8 in ?? () from /usr/lib/powerpc-linux-gnu/libstdc++.so.6
#8 0x0ff751dc in std::string::reserve(unsigned int) () from
/usr/lib/powerpc-linux-gnu/libstdc++.so.6
#9 0x0ff36774 in std::basic_istream<char, std::char_traits<char> >&
std::getline<char, std::char_traits<char>, std::allocator<char>
>(std::basic_istream<char,
std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>,
std::allocator<char> >&, char) () from /usr/lib/powerpc-linux-gnu/libstdc++.so.6
#10 0x0ff645fc in std::basic_istream<char, std::char_traits<char> >&
std::getline<char, std::char_traits<char>, std::allocator<char>
>(std::basic_istream<char,
std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>,
std::allocator<char> >&) () from /usr/lib/powerpc-linux-gnu/libstdc++.so.6
#11 0x10001f44 in (anonymous namespace)::CompleteKeys<dawgdic::Completer,
dawgdic::Guide> (dic=..., guide=..., input=0x100251e0) at dawgdic-find.cc:129
#12 0x10001a40 in main (argc=3, argv=0xffffe7a4) at dawgdic-find.cc:222
Original issue reported on code.google.com by [email protected]
on 1 Apr 2012 at 10:15
What steps will reproduce the problem?
1. download test150.txt (attached)
2. run dawgdic-build test150.txt
What is the expected output? What do you see instead?
Trying to get a built dawgdic (traced this issue back from a project I'm
working on with the `dawg` module in python.
Instead I get the error:
error: failed to insert key: +.n|+.x|a.x|c.n;b.nAgAmAC0A
What version of the product are you using? On what operating system?
using version 0.4.4 (latest) on mac os X 10.6
Please provide any additional information below.
The attached file is the output of a python process that uses
`f.write(dawg.BytesDawg()._raw_key(k, v))` to generate the lines. It works for
virtually all values I throw at it it, but very rarely (maybe one out of
several million keys) fails like this.
I'm hoping to at least find a work-around -- this library is really
extraordinary.
Thanks.
Original issue reported on code.google.com by [email protected]
on 11 Oct 2012 at 6:06
Attachments:
What steps will reproduce the problem?
1. Use DawgBuilder to create an empty DAWG;
2. create a Dictionary for this DAWG;
3. create a Guide for this Dictionary and DAWG;
4. create a Completer using this Dictionary and Guide;
5. try to use completer.Next() method
What is the expected output? What do you see instead?
Either "completer.Next()" should return "false" on first call or
GuideBuilder.Build should return false for empty DAWGs.
Instead of this, completer.Next() segfaults because Completer.FindTerminal
calls guide_->child(0) and guide_.units_ is empty.
What version of the product are you using? On what operating system?
I'm using latest dawgdic bundled with Python wrapper (0.4.4). Found this issue
trying to debug why the wrapper segfaults with empty dawgs.
Original issue reported on code.google.com by [email protected]
on 30 Sep 2012 at 2:25
This is the best dawg implementation I can find on the net. There seem to be quite some tricks in the implementation of the tree storage (various bit twiddlings and having the guide
class). I would feel much more comfortable to base code on this if there would be some basic docs explaining the rough ideas.
dawgdic 0.4.5 broke testing for out-of-tree builds:
make check-TESTS
make[2]: Entering directory `/home/jwilk/dawgdic-0.4.5/obj/test'
../../test/dawg-builder-test.sh: 7: ../../test/dawg-builder-test.sh:
../../test/dawg-builder-test: not found
FAIL: dawg-builder-test.sh
Please consider applying the attached patch. Thanks!
Original issue reported on code.google.com by [email protected]
on 17 Nov 2012 at 1:43
Attachments:
I'm working on a Python wrapper for dawgdict: https://github.com/kmike/DAWG
It is not ready yet (docs are missing and some things don't work because of
https://code.google.com/p/dawgdic/issues/detail?id=4 ) but basics (building,
saving/loading, lookups, completion) work.
It'll be great if a link will be included somewhere in docs or wiki.
Thanks for the library!
Original issue reported on code.google.com by [email protected]
on 21 Aug 2012 at 10:28
The 0.4.4 tarball is over twice as big as the 0.4.3 was. Apparently it's
because it includes the test/dawg-builder-test binary. Could you make sure that
future released of dawgic won't include any pre-built ELFs? Thanks!
Original issue reported on code.google.com by [email protected]
on 14 Nov 2012 at 1:27
The attached patch adds support for out-of-tree builds.
Original issue reported on code.google.com by [email protected]
on 26 Mar 2012 at 1:23
Attachments:
Hello,
What does it take to implement perfect hashing for DAWG? What I need is a
bidirectional 1-to-1 mapping between integer numbers and string keys.
Original issue reported on code.google.com by [email protected]
on 21 Sep 2012 at 3:30
I'm forwarding a bug that was filed by Alexandre Rebert in the Debian BTS
<http://bugs.debian.org/bug=715784>:
dawgdic-find crashes with exit status 139. We confirmed the crash by re-running
it in a fresh debian unstable installation.
The attachment contains a testcase (under ./crash) crashing the program. It
ensures that you can easily reproduce the bug. Additionally, under
./crash_info/, we include more information about the crash such as a core dump,
the dmesg generated by the crash, and its output.
Original issue reported on code.google.com by [email protected]
on 29 Nov 2013 at 1:33
Attachments:
The attached patch fixes a typo in dawgdic-build: separater → separator.
Original issue reported on code.google.com by [email protected]
on 26 Mar 2012 at 1:24
Attachments:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.