Apriori算法延伸出来的字符串统计+匹配问题

Apriori核心算法过程如下：

过单趟扫描数据库D计算出各个1项集的支持度，得到频繁1项集的集合。
连接步：为了生成，预先生成,由2个只有一个项不同的属于的频集做一个（k-2）JOIN运算得到的。
剪枝步：由于是的超集，所以可能有些元素不是频繁的。在潜在k项集的某个子集不是中的成员是，则该潜在频繁项集不可能是频繁的可以从中移去。
通过单趟扫描数据库D，计算中各个项集的支持度，将中不满足支持度的项集去掉形成。

对于一个例子：

假设使用表1的事务数据，该数据库具有9个事务，设最小支持度为2，频繁项集的极大长度为3。

表1某商店的详细事务数据

TID

Items

面包，可乐，

牛奶，可乐

牛奶，面包，

牛奶，可乐

面包，鸡蛋，麦片

牛奶，面包，可乐

牛奶，面包，鸡蛋，麦片

牛奶，面包，可乐

面包，可乐

如果要找它的情况，分别对其进行统计来完成其中的第一步（查找集合），是非常繁琐费力的，所以可以使用这个方法，先将汉字转化成字母，如下：

TID

Items

A，B，

D，B

D，A，

D，B

A，E，C

D，A，B

D，A，E，C

D，A，B

A，B

A:7	AB:4	ABC:1
B:6	AC:4	ABD:2
C:4	AD:4	ABE:0
D:6	AE:2	ACD:2
E:2	BC:1	ACE:2

然后分别统计各个字母出现的情况。这样的话，问题已经转化成一个字符串统计+匹配的问题了。

统计字符串的思路如下：

首先是对于给定的字符串组A：{"abc","bd","acd","acde","bd","ace","abd","abd","ab"};

然后是查找字符串B：{"ac","bm","ac","ce"}

1、对于给定的字符串A,设定一个标志数组flag用来标记各个字母出现的情况，其中0代表未出现,1代表出现过0-255(保证字母ASCII在255以内)。扫描A中的第一个字符串abc，在flag中做一个标记

2、用ans数组记录B中各个字符串在A中出现的次数，首先对于B中的第一个字符串ac,其中a在flag中有标记，所以继续判断c，发现c在flag中也有标记，所以ans[0]++;同样第二个字符串bm,b在flag中有标记，继续判断m，发现m在flag中未标记，故ans[1]=0,不需要加1，...继续到将ce也判断完结束

3、将flag数组中标记过的元素全部清空，使其成为一个新的空白数组，等待下次的标记。

4、字符串组B已经完成对abc的扫描，接下来再进行bd的扫描，过程同上......直至A中所有的字符串全部都验证完毕，结束整个循环

具体的统计代码如下：

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;


char s[10][10] = {"abce", "acdfhsg", "dsfebe", "asbsefds"};
char t[10][6] = {"ab","aedf"};
int ans[10];
bool flag[260];

int n = 4, m = 2;
int main()
{
    memset(ans, 0, sizeof(ans));
    memset(flag, 0, sizeof(flag));
    for(int i = 0; i < n; i++) {
        int len = strlen(s[i]);
        for(int j = 0; j < len; j++) flag[s[i][j]] = 1;

        for(int j = 'a'; j <= 'z' ; j++) printf("%d ", flag[j]); puts("");


        for(int j = 0; j < m; j ++) {
            int tlen = strlen(t[j]);
            printf("j = %d: tlen = %d\n", j, tlen);

            int k = 0;
            for( ; k < tlen; k++) {
                if(flag[t[j][k]] == 0) break;
            }
            if(k == tlen) ans[j] ++;
        }
        for(int j = 0; j < len; j++) flag[s[i][j]] = 0;
    }
    for(int i = 0; i < m; i++) printf("%d ", ans[i]); puts("");
}

秒客网

Apriori算法延伸出来的字符串统计+匹配问题

相关文章