3
$\begingroup$

I don't want to find "abc" in strings ["kkkabczzz", "shdirabckai"]

Not like that.

But bigger patterns like this:

If I have to _________, then I will ___.

["If I have to do it, then I will do it right.", "Even if I have to make it, I will not make it without Jack.", "....If I have to do, I will not...."]

I WANT TO DISCOVER NEW PATTERNS LIKE THE ABOVE. I don't already know the patterns.

I want to discover patterns in a large array or database of strings. Say going over the contents of an entire book.

Example usage of this would be finding the most common sentence structures a book uses.

The goal isn't to create the perfect algorithm or anything. I am willing to do it the brute-force way if need be like you might to find common substrings in sentences.

Is there a way to find patterns like this?

Improve this question
$\endgroup$
4
  • $\begingroup$ It seems like regular expressions would be a good fit for your problem. $\endgroup$
    – noe
    Commented Jun 12, 2022 at 12:19
  • 1
    $\begingroup$ The above example is only an example of the type of patterns I want to discover. Regex would only work if I already know the patterns. I want to discover unknown patterns. $\endgroup$
    – Mohit Gangrade
    Commented Jun 12, 2022 at 12:28
  • $\begingroup$ Ahh, I see, sorry for the confusion. $\endgroup$
    – noe
    Commented Jun 12, 2022 at 13:54
  • $\begingroup$ crosspost at stackoverflow.com/questions/72591638/… $\endgroup$
    – milahu
    Commented Nov 26, 2022 at 8:36

2 Answers 2

Reset to default
1
$\begingroup$

It's not easy, especially if you want any kind of pattern with various number of words and at any distance from each other.

The closest method I know would be to compute a huge coocurrence matrix with ngrams:

  1. Extract all the possible $n$-grams with size $n\leq N$ (for instance $N=3$).
  2. Filter out the least frequent ones. Depending on the size of the data the frequency threshold should be high enough to make the number of n-grams manageable, but not too high other some patterns may be missed.
  3. Given the resulting set of n-grams, count the number of coocurrences (number of sentences containing both) for every pair of n-grams. Store this in the coocurrence matrix.
  4. Extract the most common coocurrences from the matrix.
Improve this answer
$\endgroup$
1
$\begingroup$

The class of algorithms to search for is called "sequence alignment", usually found in bioinformatics. Example: https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm or https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm

Improve this answer
$\endgroup$
2
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$
    – Ethan
    Commented Nov 4, 2022 at 21:24
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented Nov 10, 2022 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.