在文本正文中找到一个ASCII艺术图像，并具有一定的容错性
是否有任何算法可以找到以下ASCII艺术图像？
+ + +++ +++++++ ++ ++ ++ + ++ ++ +++ ++ ++ + ++ ++ ++ +++++++ +++ 在下面的文本体内？
complete_file_here
+ + + ++ + +++ + + + ++ + + ++++ + + + + + + +++ +++ + + + + ++ ++ ++ + ++ + + + + + + ++ + ++ + + + ++ ++ + + ++++++ + + + ++ + + + + ++ + + + + + + + + ++ + ++ + + + + +++ + ++ + + + +++ + + ++ + +++++ + + + + + + + + + + + + + + + + + + + + ++ + + + ++ + + + ++
我必须突出显示黄色的ASCII艺术图像，它对应于完整的形状。 见附图：
我必须搜索包含粗糙形状的文件，但不完全，可以丢失一些+ 。 应该手动设置形状中缺失+的容差。
现在，我有两个2D数组数据数组：[100] [100]和SlimeTorpedo数组：[13] [11]。
@kjartan所述的如何进行检测的代码（3-4子弹）：
int match = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { //Compare DataArr[i][j] with SlimeTorpedoArr[i][j] //Look for "checked" position in the picture ("+"), //which corresponds to a checked position in the //slime torpedo array. //match++; } }
如何解决这个问题的一般指导是什么？
尝试使用匹配分数的暴力：
- 在“粘液鱼雷”周围定义一个“方形”; 这是一个2Darrays，宽度和高度比你的鱼雷略宽一些。
- 在该2Darrays中，根据需要将单元格标记为已选中或未选中，以创建所需的图像。
- 现在循环遍历每个字符（让我们称之为“索引”位置）在您的完整图像中，并为每个字符比较它附近的位置与2D数组中相应字符的位置。
- 在图片中查找“已检查”（或未选中）位置，该位置对应于粘液鱼雷arrays中的已检查（或未检查）位置（例如，图片中当前索引位置的上方和左侧的字符X，即匹配粘液鱼雷arrays中心点上方的状态X和左侧的Y. 对于每个这样的“匹配”，将一个“点”添加到图片中的索引位置。
现在的诀窍是 ：为了使这更有效，只需检查粘液鱼雷中的一些位置 – 例如，每10个位置甚至更少。 粗略地说，这应该将运行时间减少10倍。
这意味着您必须检查(1/10) *整个图片中每个字符the number of characters in the 2D array中的字符数。
现在跟踪全局中得分最高的位置 。 得分最高的位置应该是最佳匹配。
如果你愿意，你可以多次运行，具有不同程度的细节，例如第一次检查位置的1/20，然后是1/2，接下来，但这次只关注例如最高的20 （或50？100？）第一轮的得分位置。
（或者，您可以对得分高于某个阈值S的所有位置进行更详细的扫描）。
希望你能告诉我们你的决定是什么，有趣的问题！ 🙂
针对以下评论进行更新：
也许我的解释有点不清楚。 简而言之，伪代码，你需要做这样的事情来找到每个单元格的分数：
foreach(DataArraRow dataRow in dataArray){ foreach(IndexCell index in dataRow){ // initialy, no score for this cell in the data array: indexCell.score = 0; // Now iterate through all SlimeTorpedo cells, and compare the // symbol in it to the corresponding symbol in te data array: foreach(SlimeArrayRow slimeRow in slimeTorpedoArray){ foreach(SlimeTorpedoCell slimeCell in slimeRow){ if(IsMatchingSymbol(slimeCell.xPosition, slimeCell.yPosition, slimeCell.symbol, indexCell){ indexCell.score += 1; }else{ indexCell.score -= 1; } } } } } Function IsMatchingSymbol(x, y, slimeSymbol, indexCell){ // Find the cell in the data array corresponding to the // "slimeCell" currently being checked: var cellToCheck = getCell(indexCell.xPosition + x, indexCell.yPosition + y); if(cellToCheck.symbol == slimeSymbol){ return true; }else{ return false; } }
这显然有点乱，我不确定所有细节，但我希望它显示一个应该有用的一般概念。 当您完成迭代后，再次遍历所有单元格，并获取最高得分单元格（或沿途构建单独的高分列表 – 这可能会更快）。
您将不得不做一些更改，例如用常规For(int i=0; i < someArrayLength; i = i + levelOfDetail){ ... }或类似的东西替换ForEach循环，其中levelOfDetail是一个整数您可以调整细节级别（即要检查SlimeTorpedoArray中的细胞数）。 我相信你能解决它...;）
假设您的第一个形状已知宽度和高度参数（以字符数表示）。 让它们成为width和height 。
- 将输入编码为2D数组（或+符号）。 所以你有
int[][] inputBits = new int[height][width];你应该正确填充它。 （这是你的任务，伙计。） - 然后对较大的形状应用简单搜索（假设它也被编码到另一个2D数组中）。 每次将枢轴区域向右移动一个（枢轴区域等于第一个形状的区域）并检查枢轴区域（2Darrays）的所有元素是否等于第一个形状。 这是一个暴力算法=）
对于那些感兴趣的人，我在Java中使用XOR映射解决了这个问题：
https://bitbucket.org/bluegod1/blifoscope-java/
它还考虑到可能存在误报或重复，它可以选择指定良好匹配的最小阈值，添加自定义数据图像文件等…