在一段文本中定位ASCII艺术图像，并容忍一定的错误。

Question

有没有算法可以找到下面这个ASCII-art图像？

    +
    +
   +++
 +++++++
 ++   ++
++  +  ++
++ +++ ++
++  +  ++
 ++   ++
 +++++++
   +++

在下面的文本主体中？

完整文件在此处

（注：该链接指向一个文件下载地址）

              + +    +              ++           +       +++    +     +
 +  ++     +   + ++++    + +       +         +          +  +   +++     +++ +
     +            + +   ++      ++  ++    + ++       +     +      +  +   +
+   ++      +  ++       +          + +       ++        ++  +           +
 ++++++ + +    +   ++  +  +   +   +  ++      +         +                     +
  + +   +      +               +      ++     +  ++            +   +    + +
+++   + ++   +  +            +  +++       + +       ++                     +
  +++++  +      +                            +  + +            +   +  +
 +   +   +              +    +      +            +  +   +      +    +     +
 ++    +              +     +       ++   +          +       +           ++

我必须用黄色突出显示对应于完整形状的ASCII艺术图像。请参见附图： 我必须搜索包含大概形状但不是完全形状的文件（可能会缺少一些“+”号）。缺失一个“+”号的容错率应该手动设置。

现在，我有两个二维数组数据: [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++;
    }
}

如何解决这个问题的一般指导方针是什么？

- magister

---

请问您能提供更多关于该算法的上下文信息吗？ - Tom

可接受的不准确程度是多少？你的问题定义不清楚。 - user684934

这正是“不准确程度”的意思。有多少个缺失/多余的加号意味着它不再是相同的形状？ - thegrinner

形状始终相同。但是数据文件中包含的形状并不完全相同（有些“+”可能会丢失，但形状相同）。 我开始创建两个Java数组：一个用于数据，另一个用于形状。 - magister

我假设您不关心史莱姆鱼雷的规模或旋转？ - Eric Leschinski

Answer 1

尝试使用匹配分数进行暴力搜索：

• 在“史莱姆鱼雷”周围定义一个“正方形”，即一个2D数组，其宽度和高度略大于您的鱼雷。
• 在该2D数组中，根据需要将单元格标记为已检查或未检查，以创建所需的图像。
• 现在循环遍历完整图像中的每个字符（我们称之为“索引”位置），并针对每个字符，将其附近的位置与2D数组中相应字符的位置进行比较。
• 查找图片中对应于史莱姆鱼雷数组中的已选中（或未选中）位置的“已选中”（或未选中）位置（例如，图片中当前索引位置上面和左边的字符X与史莱姆鱼雷数组中心点上面和左边的状态X相匹配）。对于每个这样的“匹配”，在图片中的该索引位置上添加一个“点”。

现在的诀窍是：要使此方法更加有效，请仅检查史莱姆鱼雷中的某些位置 - 例如，每10个位置或更少。这应该可以将运行时间大约减少10倍。

这意味着您需要为整个图像中的每个字符检查（1/10） * 2D数组中字符数量。

现在跟踪全图最高得分的位置。最高得分的位置应该是最佳匹配。

如果您愿意，可以多次运行此过程，并使用不同程度的详细信息，例如第一次仅检查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;
   }

}

这显然有点混乱，我对所有细节都不确定，但我希望它展示了一个通用的想法，应该是可行的。当你完成迭代后，再次遍历所有单元格，并拾起得分最高的单元格（或在途中构建一个单独的高得分列表 - 那可能会更快）。

您将不得不进行一些更改，例如将ForEach循环替换为常规的For（int i = 0; i < someArrayLength; i = i + levelOfDetail）{...}或类似的内容，其中levelOfDetail是一个整数，您可以通过它来调整详细级别（即要检查 SlimeTorpedoArray 中的多少个单元格）。我相信您能够解决这个问题... ;)

- Kjartan

---

根据我在问题下的评论，我想知道形状周围的框是否需要是正方形？这取决于OP的要求，它可以是形状外面的一个字符空间。 - halfer

@halfer: 我不明白为什么它必须是正方形，但是把它想象成一个正方形似乎更容易。在图像周围包含一些更多的“空白”也无妨 - 如果我没有弄错的话，这只会提供更准确的算法（尽管可能需要稍微更长的时间，因为这将需要稍微更多的比较）。 - Kjartan

我之所以提到它，仅因为突出显示的“史莱姆鱼雷”的背景似乎非常嘈杂。+1 - halfer

感谢此页面上的所有贡献者。这是我在哪里。 @kjartan 要标记单元格很容易：或者它用“+”标记，或者它包含一个白色字符串“”。 现在，我有两个二维数组Data array: [100][100]和SlimeTorpedo array: [13][11]。抱歉，但我不明白第三点和第四点？我是初学者。 我需要做什么来计算匹配： for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { //index = i.j //查找图片中“+”所对应的“已选”位置，该位置对应于史莱姆鱼雷阵列中的已选位置。 //match++; } } - magister

@magister 我更新了我的答案，并加入了一些伪代码。希望这能让你更清楚地理解这个想法。但是恐怕你还需要自己解决具体的细节问题..祝你好运！;) - Kjartan

@Kjartan，非常感谢，现在完全清楚了。现在，让我们来编写这个想法。我会提供解决方案的链接。我几天后回来。 - magister

Answer 2

假设你已经知道了第一个形状的宽度和高度参数（以字符数为单位）。让它们分别为width和height。

• 将输入编码成二维位数组（或加号符号）。因此，您有int[][] inputBits = new int[height][width];，您应该正确地填充它。（这是您的任务，伙计。）
• 然后在较大的形状上应用简单的搜索（假设它也被编码为另一个二维数组）。每次将中心区域向右移动一位（中心区域等同于第一个形状的区域），并检查中心区域（2D数组）是否所有元素都等于第一个形状。这是一种暴力算法=）

- Juvanis

---

只会找到完全匹配的内容，如果需要进行不完全匹配的调整，但是没有说明什么构成了匹配，我认为这个问题是无法回答的。 - user684934

@bdares，我的算法效率值得怀疑，但它可以找到精确匹配，我认为 OP 想要检测精确匹配。 - Juvanis

匹配是指算法检测到一个形状，但并非完全相同的形状（不准确：缺少一些“+”字符）。 - magister

你可以很容易地将其变成“模糊”匹配。在每一步中，不要检查枢轴区域是否具有所有相等的元素，而是检查它是否具有至少A个相等的元素和不超过B个不相等的元素。然后返回具有最少不匹配项的枢轴区域。 - Kevin

Answer 3

对于那些感兴趣的人，我使用Java中的XOR映射解决了这个问题：

https://bitbucket.org/bluegod1/blifoscope-java/

它还考虑到可能存在误报或重复，它有指定良好匹配的最小阈值选项，添加自定义数据图像文件等选项...

- BLuEGoD