比较多个数组以找到它们在 C 中的相似性

Question

我是 C 语言的初学者，我正在尝试找出一种解决方案来比较多个数组并根据哪些元素相同来找出它们的百分比相似度。

例如，我们有以下名为 Library 的结构，其中包含文章：

typedef struct
{
  int articleId;
  int count;
  int bibliography[3];
} Article;

typedef struct
{
  Article **articles;
  int count;
  int allocated;
} Library;

填充库的示例如下所示：

articleId   bibliography
000         [222,111]
111         [333,222]
222         [111]
333         [222,111]

我的目标是找出所有文章及其参考书目之间的相似性，而不管它们的顺序如何。换句话说，哪些文章引用了相同的文章？

我所说的相似性是什么意思：当比较两个数组时，我们检查另一个数组中具有相同整数的整数的数量。然后我们将这个数字除以较大数组的长度，得到我们的相似度。

例如，000 和 333 相似度为 100%，222 和 333 相似度为 50%，111 和 222 相似度为 0%，依此类推。

我特别有麻烦，因为数组的长度都不同。有人有什么想法吗？我的方法将包括嵌套的 for 循环，但我不确定这是否是正确的方向。

我在代码中构建算法的尝试：

    double citationSimilarity (Library *lib)
{
    int currentCitation[3];
    int comparingCitation[3];
    int[] similarityResults;

    int similar = 0; //amount of similar citations
    double similarity = 0;
    int total = 0; //highest total amount of citations

    for(int i = 0; i < lib->count; i ++){
      for(int j = 1; j < lib->count; j ++){
              similar = 0;
      similarity = 0;
        for(int k = 0; k < lib->articles[i]->count; k ++){
          for(int l = 0; l < lib->articles[j]->count; l ++){
            currentCitation[k] = lib->articles[i]->bibliography[k];
            comparingCitation[l] = lib->articles[j]->bibliography[l];
            if(lib->articles[i]->articleId != lib->articles[j]->articleId){
            if(currentCitation[k] == comparingCitation[l]){
                similar++;
                if(similar != 0){
                    similarity = (double)similar / (double)getLargerBibliography(lib->articles[j]->count, lib->articles[i]->count);
                }
              printf ("Great success! %d and %d have the similarity %lf \n",lib->articles[i]->articleId, lib->articles[j]->articleId, similarity);
            }
            }
          }
        }
      }
   }
}



int getLargerBibliography (int bib_a, int bib_b)
{

int max;
int min;


  if (bib_a >= bib_b)
  {
    max = bib_a;
    min = bib_b;
  }
  else
  {
    max = bib_b;
    min = bib_a;
  }

  return max;

}

Answer 1

使用合并比较两个数组

对第一个数组的元素进行排序（以后称为 array1）。
对第二个数组（以后称为 array2）的元素进行排序。
将 i 设置为 0。
将 j 设置为 0。
将 count 设置为 0。
虽然i小于array1中的元素个数，
而j小于array2中的元素个数,
1. 如果 array1[i] 小于 array2[j],
  1. 递增 i.
2. 否则，
  1. 如果 array1[i] 大于 array2[j],
    1. 递增 j.
  2. 否则，
    1. 递增 count.
    2. 递增 i.
    3. 递增 j.
找出array1的长度和array2的长度中的最大值。
将 count 除以两个数组长度中的最大值。

这支持数组中的重复元素。

复杂度因使用的排序算法而异。使用通用排序算法，比较每一对需要 O(1) 额外内存和 O(N log N) 时间。但如果值是真正的整数，则可以实现 O(N) 排序，但会占用一些内存。无论哪种方式，每个数组只需要执行一次排序，而不是每次比较都执行一次，因此排序成本被摊销。

使用集合差异比较两个数组

这是一个 O(N) 内存和 O(N) 时间解决方案，即使对于非整数键也适用。循环的每次通过都更昂贵，因此可能需要很大的 N 才能获得任何收益。

创建一组。（可以使用关联数组。）
对于其中一个数组中的每个值，
1. 将其添加到集合中。
  （如果使用关联数组，请使用值作为键，并使用任何值作为值。）
对于另一个数组中的每个值，
1. 如果该值在之前创建的集合中，
  1. 加一。
求第一个数组的长度。
求出第二个数组的长度。
找出两个数组长度中的最大值。
将计数除以两个数组长度中的最大值。

由于它不会破坏集合，您可以预先为每个数组创建并在比较不同的数组对时重用它！

这不支持重复元素，但可以很简单地进行调整。

比较多个数组以找到它们在 C 中的相似性

Comparing multiple arrays to find their similarity in C

c

arrays

loops

compare