Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect output regex on certain inputs. #7

Closed
IQuick143 opened this issue May 12, 2019 · 3 comments
Closed

Incorrect output regex on certain inputs. #7

IQuick143 opened this issue May 12, 2019 · 3 comments

Comments

@IQuick143
Copy link
Contributor

When the words fed into the trie are a prefix of an other word, the regex outputted is not correct.

Example code used to reproduce bug:

import triegex

def RegexFromList(listOfWords):
	t = triegex.Triegex()
	for i in listOfWords:
		t.add(i)
	return t.to_regex()

print(RegexFromList(["TEST", "TE", "TEXT", "BANANA"]))

This code outputs: (?:XT\b|TE\b|~^(?#match nothing))
Which happens to match TE correctly but matches XT too and doesn't match TEXT, TEST, BANANA as would be expected.

Expected Regex would be: (?:TE(?:\b|XT\b|ST\b)|BANANA\b|~^(?#match nothing)) or equivalent.

@IQuick143
Copy link
Contributor Author

I've written a fix for this bug but it involves rewriting the whole TrierexNode.to_regex() method and my implementation is recursive (but very simple), all unit tests pass.

Is the recursion okay, or must I rewrite it into a loop? (not trivial in this case)

@IQuick143
Copy link
Contributor Author

Either way I've made an iterative implementation.

IQuick143 added a commit to IQuick143/triegex that referenced this issue May 12, 2019
ZhukovAlexander added a commit that referenced this issue May 15, 2019
Fixed Issue #7 and fixed grammar
@ZhukovAlexander
Copy link
Owner

@IQuick143 thanks for your work, I'll release the new version to PyPI as soon as I can.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants