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

feat: Implement Bitap Algorithm for approximate string matching #589

Open
asmit27rai opened this issue Mar 3, 2025 · 1 comment · May be fixed by #599
Open

feat: Implement Bitap Algorithm for approximate string matching #589

asmit27rai opened this issue Mar 3, 2025 · 1 comment · May be fixed by #599

Comments

@asmit27rai
Copy link

Description

The Bitap Algorithm (also known as the Shift-Or Algorithm) is a bit-parallel algorithm used for approximate string matching. It is particularly useful for fuzzy string matching and searching with errors (e.g., allowing a certain number of mismatches).

This issue involves implementing the Bitap Algorithm in the pydatastructs.strings.algorithms module.

Proposed Implementation

  • Add a function bitap(text: str, query: str, max_errors: int = 0) -> DynamicOneDimensionalArray to the algorithms.py file.
  • The function should return the starting positions of all matches of the query in the text, allowing up to max_errors mismatches.
  • Include unit tests for the new function.
  • Update the __all__ list to include the bitap function.
@asmit27rai
Copy link
Author

@Kishan-Ved I am working on this issue....

@asmit27rai asmit27rai linked a pull request Mar 10, 2025 that will close this issue
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

Successfully merging a pull request may close this issue.

1 participant