java协同过滤算法,
00-1010后台分析准备的实现写在最后。
00-1010最近有个新要求，要求在后台设置一个复杂的关系表达式。根据用户指定的ID，分析用户是否满足该条件，并在后台设置类似禅宗的搜索条件。
但不同的是，禅宗只有两组，每组最多三个条件。
然而在我们这边，群体之间的关系可能更复杂。群中有群，每一个条件都是与或相关的。出于保密原因，原型不会发出。
看到这个需求，作为一个后端，首先想到的就是QLEpress这样的表达式框架。只要构建一个表达式，就可以通过解析表达式快速筛选目标用户，可惜前端同学退出了。作为一个使用vue或者react的数据驱动框架，要把表达式转换成上述形式太难了，所以我想了想，决定自己定义一个数据结构来实现表达式解析。方便前端学生处理。
00-1010虽然是一个类实现的表达式，但本质上还是一个表达式。我们来列举一个简单的表达式：假设条件为A，B，C，D，我们随意构造一个表达式：
布尔结果=a100 b=10 (c！=3 d 50)
通过分析这些表达式，我们可以发现这些表达式具有共同的属性：
过滤字段(A，B，C，D)，判断条件(大于，小于，不等于等。)，对比值(100年100)。
此外，还有关联关系(和，或)和计算优先级.
所以我们简化了表达式：
使a100=A，b=10=B，c！=3=C，d50=D，所以我们得到：
结果=A B (C D)
现在问题来了，优先权怎么处理？
上面的表达式，显然是大学学过的标准中阶表达式，我们来画一下它的树形图：
根据这个图，我们可以清楚地看到，A和B，C和D处于同一水平。所以我们根据这个理论设计一个深度的层次概念，标记出来，然后区分节点的类型。我们可以得到：
我们可以看到，作为叶子节点(上图中绿色的部分)，相对于它的计算关系，必须先计算，所以对于深度优先，我们只需要考虑非叶子节点，也就是上图中蓝色的节点部分，这样就得到计算优先级,的概念，我们可以把它转换成表达式的深度。
我们来看上图。Deep1的关系是Deep2中A和B、C和D两个表达式计算出来的结果是AND-OR。假设A和B是G1，C和D是G2，那么我们发现有两种类型的关系节点关联，一种是条件条件，一种是组群。
至此，这个类的雏形基本确定。该类包含关联关系(关系)、判断字段(字段)、运算符(运算符)、值、类型(类型)和深度(深度)。
但是，有一个问题。在上面的分析中，我们将表达式转换成一棵树。现在我们试着还原一下，这样可以一目了然的得到其中一个表达式：
结果=(A B)(C D)
显然，这与我们最初的表达方式并不一致。这是因为我们只能记录表达式的计算顺序，而不能完整准确地表达这个表达式。这是因为在解析表达式的过程中，不仅有深度，还有时序关系，即从左到右的顺序。这时，原表达式中G1的深度实际上应该是1而不是2。然后，我们引入序号的概念，把原始树变成一个有向图，即：
根据这个图，我们可以还原出一个唯一的表达式：result=A B (C D)。
好了，我们分析了很久，原理说完了。让我们回到原来的问题：前后端怎么实现?想象反对上面的图片，它似乎仍然不可能处理它，因为这个结构仍然太复杂了。对于前端来说，数据要方便。
历的，对于后端，数据最好是方便处理的，于是这时候我们需要将上面这个图转换成一个数组。
实现方式
上面说到了需要一个数组的结构，我们具体分析一下这个部分
我们发现作为叶子节点，可以始终优先计算，所以我们可以将其压缩，并将关系放置在其中一个表达式中形成 ^A -> &&B或 A&& -> B$ 的形式，这里我用正则的开始(^) 和结束($) 表示了一下开始 和 结束 的概念,这里为了与产品原型保持一致我们用第一种方式，即关系符号表示与前一个元素的关系，于是我们再分析一下：
再对序号进行改造：
于是我们得到最终的数据结构：
@Data @AllArgsConstructor @NoArgsConstructor @Accessors(chain = true) public class ExpressDto { /** * 序号 */ private Integer seq; /** * 深度（运算优先级） */ private Integer deep; /** * 关系运算符 */ private String relation; /** * 类型 */ private String type; /** * 运算条件 */ private String field; /** * 逻辑运算符 */ private String operator; /** * 运算值 */ private String values; /** * 运算结果 */ private Boolean result; }现在数据结构终于完成，既方便存储，又（相对）方便前台展示，现在构造一个稍微复杂的表达式
A &&(( B C ) (D && E)) && F
换成数组对象，开始用BEGIN标识，表达式类型用CONDITION表示，组用GROUP表示。
[ {"seq":1,"deep":1,relation:"BEGIN","type":"CONDITION","field"="A"...}, {"seq":2,"deep":1,relation:"AND","type":"GROUP","field":""...}, {"seq":3,"deep":2,relation:"BEGIN","type":"GROUP","field":""...}, {"seq":4,"deep":3,relation:"BEGIN","type":"CONDITION","field":"B"...}, {"seq":5,"deep":3,relation:"OR","type":"CONDITION","field":"C"...}, {"seq":6,"deep":2,relation:"OR","type":"GROUP","field":""...}, {"seq":7,"deep":3,relation:"BEGIN","type":"CONDITION","field":"D"...}, {"seq":8,"deep":3,relation:"AND","type":"CONDITION","field":"E"...}, {"seq":9,"deep":1,relation:"AND","type":"CONDITION","field":"F"...} ]现在就剩最后一个问题：如何通过这个json对数据进行过滤了
由于数组对象的本质依旧是一个中缀表达式，所以其本质依旧是一个中缀表达式的解析，关于解析原理，这里不多介绍，简单的说就是通过数据栈和符号栈根据括号（在我们这里称为组）进行遍历，想了解更多，可以通过下面这篇文章复习一下
于是我们定义三个变量：
//关系 栈 Deque<String> relationStack=new LinkedList(); //结果栈 Deque<Boolean> resultStack=new LinkedList(); // 当前深度 Integer nowDeep=1;
通过遍历数组，将关系与结果入栈，当发现需要优先计算的时候，从结果栈中取出两个值，从关系栈中取出关系运算符，计算后再次入栈，等待下一次计算
for (ExpressDto expressDto:list) { if(!StringUtils.equals(expressDto.getType(),"GROUP")){ //TODO 进行具体单个表达式计算并获取结果 resultStack.push(expressDto.getResult()); // 将关系放入栈中 relationStack.push(expressDto.getRelation()); if(deep==0 && resultStack.size()>1){ //由于已处理小于0的deep，当前deep理论上是>=0的，0表示同等级，需要立即运算 relationOperator(relationStack, resultStack); } }else{ // 将关系放入栈中 relationStack.push(expressDto.getRelation()); } } private void relationOperator(Deque<String> relationStack, Deque<Boolean> resultStack) { Boolean lastResult= resultStack.pop(); Boolean firstResult= resultStack.pop(); String relation=relationStack.pop(); if(StringUtils.equals(relation,"AND")){ resultStack.push(firstResult&& lastResult) ; return; } if(StringUtils.equals(relation,"OR")){ resultStack.push( firstResult lastResult); return; }else{ throw new RuntimeException("表达式解析异常：关系表达式错误"); } }再说一下注意的边界事项：
1.首先我们同级中关联关系仅存在且、或两种，而这两种的计算优先级是一样的。故同一个Deep下，从左到右依次遍历计算即可。
2.当遇到GROUP的类型时，相当于遇到了"(",我们可以发现它后面的元素Deep +1 直到Deep -1为止")"结束，而括号中的元素需要优先计算，也就是说"()"所产生优先级通过Deep 和Type=GROUP 共同控制
3.当Deep减少时，意味着遇到了")"，此时结束的Group的数量等于Deep减少的数量，针对")"结束，每遇到一个")" 都需要对该级括号进行检查，是否同级别的元素是否已经计算完毕。
/** * 处理层级遗留元素 * * @param relationStack * @param resultStack */ private void computeBeforeEndGroup(Deque<String> relationStack, Deque<Boolean> resultStack) { boolean isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");//防止group中仅有一个判断条件 while(!isBeginSymbol){//上一个运算符非BEGIN，说明该group中还有运算需要优先处理，正常这里应该仅循环一次 relationOperator(relationStack, resultStack); isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN"); } if(isBeginSymbol){ relationStack.pop();//该优先级处理完毕，将BEGIN运算符弹出 } }4.当遍历结束发现最后一个元素Deep不等于1时，意味着有括号结束，这时，同样需要进行括号结束处理
最后上完整代码：
/** * 表达式解析器 * 表达式规则： * 关系relation属性有：BEGIN、AND、OR 三种 * 表达式类型 Type 属性有：GROUP、CONDITION 两种 * 深度 deep 属性 根节点为 1，每增加一个括号（GROUP）deep+1，括号结束deep-1 * 序号req：初始值为1，往后依次递增，用于防止表达式解析顺序错误 * exp1：表达式：A &&(( B C ) (D && E)) && F * 分解对象： * [ * {"seq":1,"deep":1,relation:"BEGIN","type":"CONDITION","field"="A"...}, * {"seq":2,"deep":1,relation:"AND","type":"GROUP","field":""...}, * {"seq":3,"deep":2,relation:"BEGIN","type":"GROUP","field":""...}, * {"seq":4,"deep":3,relation:"BEGIN","type":"CONDITION","field":"B"...}, * {"seq":5,"deep":3,relation:"OR","type":"CONDITION","field":"C"...}, * {"seq":6,"deep":2,relation:"OR","type":"GROUP","field":""...}, * {"seq":7,"deep":3,relation:"BEGIN","type":"CONDITION","field":"D"...}, * {"seq":8,"deep":3,relation:"AND","type":"CONDITION","field":"E"...}, * {"seq":9,"deep":1,relation:"AND","type":"CONDITION","field":"F"...} * ] * * exp2:(A B && C)(D && E && F) * [ * {"seq":1,"deep":1,relation:"BEGIN","type":"GROUP","field":""...}, * {"seq":2,"deep":2,relation:"BEGIN","type":"CONDITION","field":"A"...}, * {"seq":3,"deep":2,relation:"OR","type":"CONDITION","field":"B"...}, * {"seq":4,"deep":2,relation:"AND","type":"CONDITION","field":"C"...}, * {"seq":5,"deep":1,relation:"OR","type":"GROUP","field":""...}, * {"seq":6,"deep":2,relation:"BEGIN","type":"CONDITION","field":"D"...}, * {"seq":7,"deep":2,relation:"AND","type":"CONDITION","field":"E"...}, * {"seq":8,"deep":2,relation:"AND","type":"CONDITION","field":"F"...} * ] * * * @param list * @return */ public boolean expressProcessor(List<ExpressDto>list){ //关系 栈 Deque<String> relationStack=new LinkedList(); //结果栈 Deque<Boolean> resultStack=new LinkedList(); // 当前深度 Integer nowDeep=1; Integer seq=0; for (ExpressDto expressDto:list) { // 顺序检测，防止顺序错误 int checkReq=expressDto.getSeq()-seq; if(checkReq!=1){ throw new RuntimeException("表达式异常：解析顺序异常"); } seq=expressDto.getSeq(); //计算深度（计算优先级），判断当前逻辑是否需要处理括号 int deep=expressDto.getDeep()-nowDeep; // 赋予当前深度 nowDeep=expressDto.getDeep(); //deep 减小，说明有括号结束，需要处理括号到对应的层级，deep减少数量等于组（"）"）结束的数量 while(deep++ < 0){ computeBeforeEndGroup(relationStack, resultStack); } if(!StringUtils.equals(expressDto.getType(),"GROUP")){ //TODO 进行具体单个表达式计算并获取结果 resultStack.push(expressDto.getResult()); // 将关系放入栈中 relationStack.push(expressDto.getRelation()); if(deep==0 && resultStack.size()>1){ //由于已处理小于0的deep，当前deep理论上是>=0的，0表示同等级，需要立即运算 relationOperator(relationStack, resultStack); } }else{ // 将关系放入栈中 relationStack.push(expressDto.getRelation()); } } //遍历完毕，处理栈中未进行运算的节点 while(nowDeep-- > 0){ // 这里使用 nowdeep>0 的原因是最后deep=1的关系表达式也需要进行处理 computeBeforeEndGroup(relationStack, resultStack); } if(resultStack.size()!=1){ throw new RuntimeException("表达式解析异常:解析结果数量异常解析数量:"+resultStack.size()); } return resultStack.pop(); } /** * 处理层级遗留元素 * * @param relationStack * @param resultStack */ private void computeBeforeEndGroup(Deque<String> relationStack, Deque<Boolean> resultStack) { boolean isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");//防止group中仅有一个判断条件 while(!isBeginSymbol){//上一个运算符非BEGIN，说明该group中还有运算需要优先处理，正常这里应该仅循环一次 relationOperator(relationStack, resultStack); isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN"); } if(isBeginSymbol){ relationStack.pop();//该优先级处理完毕，将BEGIN运算符弹出 } } /** * 关系运算处理 * @param relationStack * @param resultStack */ private void relationOperator(Deque<String> relationStack, Deque<Boolean> resultStack) { Boolean lastResult= resultStack.pop(); Boolean firstResult= resultStack.pop(); String relation=relationStack.pop(); if(StringUtils.equals(relation,"AND")){ resultStack.push(firstResult&& lastResult) ; return; } if(StringUtils.equals(relation,"OR")){ resultStack.push( firstResult lastResult); return; }else{ throw new RuntimeException("表达式解析异常：关系表达式错误"); } }简单写了几个测试用例：
/** * 表达式：A */ @Test public void expTest0(){ ExpressDto E1=new ExpressDto().setDeep(1).setResult(false).setSeq(1).setType("CONDITION").setField("A").setRelation("BEGIN"); List<ExpressDto> list = new ArrayList(); list.add(E1); boolean re=expressProcessor(list); Assertions.assertFalse(re); } /** * 表达式：(A && B)(C D) */ @Test public void expTest1(){ ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("GROUP").setRelation("BEGIN"); ExpressDto E2=new ExpressDto().setDeep(2).setResult(true).setSeq(2).setType("Condition").setField("A").setRelation("BEGIN"); ExpressDto E3=new ExpressDto().setDeep(2).setResult(false).setSeq(3).setType("Condition").setField("B").setRelation("AND"); ExpressDto E4=new ExpressDto().setDeep(1).setSeq(4).setType("GROUP").setRelation("OR"); ExpressDto E5=new ExpressDto().setDeep(2).setResult(true).setSeq(5).setType("Condition").setField("C").setRelation("BEGIN"); ExpressDto E6=new ExpressDto().setDeep(2).setResult(false).setSeq(6).setType("Condition").setField("D").setRelation("OR"); List<ExpressDto> list = new ArrayList(); list.add(E1); list.add(E2); list.add(E3); list.add(E4); list.add(E5); list.add(E6); boolean re=expressProcessor(list); Assertions.assertTrue(re); } /** * 表达式：A && (B C && D) */ @Test public void expTest2(){ ExpressDto E1=new ExpressDto().setDeep(1).setResult(true).setSeq(1).setType("Condition").setField("A").setRelation("BEGIN"); ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("AND"); ExpressDto E3=new ExpressDto().setDeep(2).setResult(false).setSeq(3).setType("Condition").setField("B").setRelation("BEGIN"); ExpressDto E4=new ExpressDto().setDeep(2).setResult(false).setSeq(4).setType("Condition").setField("C").setRelation("OR"); ExpressDto E5=new ExpressDto().setDeep(2).setResult(true).setSeq(5).setType("Condition").setField("D").setRelation("AND"); List<ExpressDto> list = new ArrayList(); list.add(E1); list.add(E2); list.add(E3); list.add(E4); list.add(E5); boolean re=expressProcessor(list); Assertions.assertFalse(re); E4.setResult(true); list.set(3,E4); re=expressProcessor(list); Assertions.assertTrue(re); E1.setResult(false); list.set(0,E1); re=expressProcessor(list); Assertions.assertFalse(re); } @Test public void expTest3(){ ExpressDto E1=new ExpressDto().setDeep(1).setResult(true).setSeq(1).setType("Condition").setField("A").setRelation("BEGIN"); ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("OR"); ExpressDto E3=new ExpressDto().setDeep(2).setResult(true).setSeq(3).setType("Condition").setField("B").setRelation("BEGIN"); ExpressDto E4=new ExpressDto().setDeep(2).setSeq(4).setType("GROUP").setRelation("AND"); ExpressDto E5=new ExpressDto().setDeep(3).setResult(true).setSeq(5).setType("Condition").setField("C").setRelation("BEGIN"); ExpressDto E6=new ExpressDto().setDeep(3).setResult(false).setSeq(6).setType("Condition").setField("D").setRelation("OR"); List<ExpressDto> list = new ArrayList(); list.add(E1); list.add(E2); list.add(E3); list.add(E4); list.add(E5); list.add(E6); boolean re=expressProcessor(list); Assertions.assertTrue(re); } /** * 表达式：A &&(( B C ) (D && E)) */ @Test public void expTest4(){ ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("CONDITION").setResult(true).setField("A").setRelation("BEGIN"); ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("AND"); ExpressDto E3=new ExpressDto().setDeep(2).setSeq(3).setType("GROUP").setRelation("BEGIN"); ExpressDto E4=new ExpressDto().setDeep(3).setSeq(4).setType("CONDITION").setResult(true).setField("B").setRelation("BEGIN"); ExpressDto E5=new ExpressDto().setDeep(3).setSeq(5).setType("CONDITION").setResult(true).setField("C").setRelation("OR"); ExpressDto E6=new ExpressDto().setDeep(2).setSeq(6).setType("GROUP").setRelation("OR"); ExpressDto E7=new ExpressDto().setDeep(3).setSeq(7).setType("CONDITION").setResult(false).setField("D").setRelation("BEGIN"); ExpressDto E8=new ExpressDto().setDeep(3).setSeq(8).setType("CONDITION").setResult(false).setField("E").setRelation("AND"); List<ExpressDto> list = new ArrayList(); list.add(E1); list.add(E2); list.add(E3); list.add(E4); list.add(E5); list.add(E6); list.add(E7); list.add(E8); boolean re=expressProcessor(list); Assertions.assertTrue(re); } /** * 表达式：(A) */ @Test public void expTest5(){ ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("GROUP").setRelation("BEGIN"); ExpressDto E2=new ExpressDto().setDeep(2).setResult(true).setSeq(2).setType("Condition").setField("A").setRelation("BEGIN"); List<ExpressDto> list = new ArrayList(); list.add(E1); list.add(E2); boolean re=expressProcessor(list); Assertions.assertTrue(re); E2.setResult(false); list.set(1,E2); Assertions.assertFalse(expressProcessor(list)); }测试结果：
写在最后
至此，一个表达式解析就完成了，让我们回过来再看这张图：
我们可以发现，其实Seq3 的作用其实仅仅是标识了一个组的开始并记录该组与同级别的其他元素的关联关系，其实，这里还可以进行一次优化：我们发现每当一个组的开始的第一个节点其前置关联关系一定是Begin，Deep+1，实际上我们可以考虑将Group的关联关系放在这个节点上，然后仅仅通过Deep的增减控制组的关系，这样，我们就不需要类型为表达式或组的这个字段了，而且数组长度也会因此减少，但是个人认为理解起来会麻烦一点。这里说一下大概改造思路，代码就不放出来了：
将代码中有关Type="GROUP"的判断改为通过deep的差值=1进行判断深度判断入栈逻辑修改在存储关系符号的时候还要存储一下这个关系符号对应的深度在处理同深度遗留元素时,即：computeBeforeEndGroup() 方法中， 原方法是通过Begin元素进行区分Group是否处理完成，现需要改成通过下一个符号的深度是否和当前深度是否相同进行判断，并删除掉有关BEGIN元素的弹出的逻辑以上就是基于Java实现一个复杂关系表达式过滤器的详细内容，更多关于Java表达式过滤器的资料请关注盛行IT其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。