1
$\begingroup$

Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams.

  1. The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is 6.

  2. The total cardinality of all subsets for those n-grams is sum(1,1,1,2,2,3)=10

So, given set T, what are the formulae for #1 and #2?

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by Evil, David Richerby, Rick Decker, Luke Mathieson, Juho Oct 15 '17 at 10:51

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Your "ordered sequential n-grams" appear to be simply "subsets". Is that what you intended? $\endgroup$ – j_random_hacker Sep 21 '17 at 19:53
  • $\begingroup$ Yes! Some background: I use those terms because I am trying to solve this in the context of a lookup for full-text search. We have a string and break it into n-grams and then search those. We need to know the total number tokens that get searched when the number of terms in the query is high, and optimize. $\endgroup$ – binarymax Sep 21 '17 at 21:39
  • 1
    $\begingroup$ @j_random_hacker, not exactly. If $ABC$ is a string then the asker considers only nonempty substrings of $ABC$, namely $A,B,C, AB, BC, $ and $ABC$. The problem statement of course needs better wording. $\endgroup$ – fade2black Sep 22 '17 at 6:23
  • $\begingroup$ @evil - I find it strange that this question was closed, considering the commentary was clearly understood and the question answered. Please be specific on what further clarity you require. $\endgroup$ – binarymax Oct 31 '17 at 20:45
3
$\begingroup$

Let $|T| = n$. Then

  1. the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.

  2. The total cardinality of all subsets for those $n$-grams is $$\sum_{k=1}^nk(n-k+1) = (n+1)\sum_{k=1}^nk - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

  1. $\frac{3\times 4}{2} = 6$
  2. $\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10 $
|cite|improve this answer
$\endgroup$

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