유사한 텍스트가있는 기사를 찾는 알고리즘

유사한 텍스트가있는 기사를 찾는 알고리즘

---

데이터베이스 (제목, 텍스트 포함)에 많은 기사가 있습니다. 질문을 할 때 Stack Overflow의 "관련 질문"과 같이 X 개의 가장 유사한 기사를 찾는 알고리즘을 찾고 있습니다.

나는 이것을 위해 인터넷 검색을 시도했지만 모든 기사를 다른 모든 기사와 비교하고 어딘가에 유사성을 저장하는 것과 같은 다른 "유사한 텍스트"문제에 대한 페이지 만 찾았습니다. 그래서 방금 입력 한 텍스트에 대해 "실시간"으로이 작업을 수행합니다.

어떻게?

---

편집 거리는 철자 / 단어 순서에 따라 달라질 수 있으며 실제로 검색하려는 문서의 크기와 수를 고려할 때 Will보다 계산 비용이 훨씬 더 많이 들기 때문에 가능성이 없습니다.

Lucene과 같은 것이 갈 길입니다. 모든 문서를 색인 한 다음 주어진 문서와 유사한 문서를 찾으려면 주어진 문서를 쿼리로 변환하고 색인을 검색합니다. 내부적으로 Lucene은 tf-idf 및 반전 된 인덱스 를 사용하여 전체 프로세스가 컬렉션의 총 문서 수가 아니라 일치 할 수있는 문서 수에 비례하는 시간이 걸리도록합니다.

---

그것은 유사에 대한 당신의 정의에 달려 있습니다.

편집 - 거리 알고리즘 (라틴어) 사전 제안의 표준 알고리즘이며, 전체 텍스트 작업 할 수 있습니다. 두 텍스트는 기본적으로 같은 순서로 같은 단어 (eh 글자)가 있으면 유사합니다. 따라서 다음 두 서평은 상당히 유사합니다.

1) "이것은 훌륭한 책입니다"

2) "이것들은 훌륭한 책이 아닙니다."

(제거, 삽입, 삭제 또는 변경하여 (2)를 (1)로 바꾸는 문자의 수를 '편집 거리'라고합니다.)

이를 구현하려면 모든 리뷰를 프로그래밍 방식으로 방문하는 것이 좋습니다. 이것은 들리는 것만 큼 비용이 많이 들지 않을 수 있으며 너무 비용이 많이 드는 경우 백그라운드 작업으로 비교를 수행하고 데이터베이스 필드 자체에 n- 가장 유사한 항목을 저장할 수 있습니다.

또 다른 접근 방식은 (라틴어) 언어의 구조를 이해하는 것입니다. 짧은 (대문자 또는 따옴표가없는) 단어를 제거하고 공통되거나 고유 한 단어 (또는 접두사)에 가중치를 할당하는 경우 베이지 안식 비교를 수행 할 수 있습니다. 다음의 두 서평은 유사 할 수 있으며 유사하다고 판명 될 수 있습니다.

3) "프랑스 혁명은 어쩌구 전쟁과 평화 어쩌구 프랑스." -> 프랑스 / 프랑스 (2) 혁명 (1) 전쟁 (1) 평화 (1) (사전은 프랑스와 프랑스어를 결합하는 데 사용되었습니다)

4) "이 책은 프랑스 요리의 혁명이다." -> 프랑스 (1) 혁명 (1)

이를 구현하려면 리뷰가 작성 / 업데이트 될 때 '키워드'를 식별하고 유사한 리뷰를 찾으려면 쿼리의 where-clause에서 이러한 키워드를 사용합니다 (이상적으로는 데이터베이스에서 지원하는 경우 '전체 텍스트'검색) ), 아마도 발견 된 후보를 채점하기위한 결과 집합의 사후 처리와 함께.

책에도 카테고리가 있습니다. 프랑스에서 설정된 스릴러는 프랑스의 역사 연구와 비슷합니까? 제목과 텍스트 이외의 메타 데이터는 결과를 관련성있게 유지하는 데 유용 할 수 있습니다.

---

이 링크 의 튜토리얼은 필요한 것처럼 들립니다. 따라하기 쉽고 매우 잘 작동합니다.

그의 알고리즘은 공통 하위 문자열과 해당 하위 문자열의 공통 순서를 모두 보상하므로 유사한 제목을 아주 잘 선택해야합니다.

---

내가 사용하는 인덱스 기사에 제안 아파치 루씬 , 고성능, 자바로 작성 완전한 기능을 갖춘 텍스트 검색 엔진 라이브러리를. 이는 전체 텍스트 검색이 필요한 거의 모든 애플리케이션, 특히 크로스 플랫폼에 적합한 기술 입니다. 색인이 생성되면 관련 기사를 쉽게 찾을 수 있습니다.

---

사용되는 일반적인 알고리즘 중 하나는 Self-Organizing Map 입니다. 기사를 자동으로 분류하는 신경망 유형입니다. 그런 다음지도에서 현재 기사가 있고 그 근처의 모든 기사가 관련되어있는 위치를 간단히 찾을 수 있습니다. 알고리즘의 중요한 부분은 입력을 벡터화 하는 방법 입니다. 텍스트로 작업하는 방법에는 여러 가지가 있습니다. 문서 / 제목을 해시 할 수 있고, 단어를 세고이를 n 차원 벡터로 사용할 수 있습니다. 도움이되기를 바라지 만 AI에서 끝없는 여정을 위해 Pandora의 상자를 열었을 수도 있습니다.

---

그래서 질문의 본문 텍스트가 아니라 제목에 대해서만 비교를 수행하므로 다소 짧은 문자열에서만 수행됩니다.

기사 제목과 키워드에 알고리즘을 사용할 수 있습니다 (어떻게 보이는지 알 수 없음). 더 많은 CPU를 태울 시간이 있다면 기사의 초록에도.

---

전체 텍스트에 대한 Lucene 제안을 두 번째로 고려하지만 Java는 요구 사항이 아닙니다. .NET 포트를 사용할 수 있습니다 . 또한 C 포트 인 Lucy를 포함하여 다른 프로젝트에 대한 링크 는 기본 Lucene 페이지 를 참조하십시오 .

---

아마도 당신이 찾는 것은 의역을하는 것 입니다. 나는 이것에 대해 피상적 지식 만 가지고 있지만, 패러 프레이징은 텍스트의 두 구절이 실제로 동일한 것을 의미 하는지를 결정 하는 자연어 처리 개념 입니다. 비록 완전히 다른 단어를 사용할 수도 있습니다.

안타깝게도이 작업을 수행 할 수있는 도구를 알지 못합니다 (하지만 찾는 데 관심이 있습니다).

---

SQL Server 전체 텍스트 인덱스를 사용하여 현명한 비교를 얻을 수 있습니다. SO가 유사한 질문을 반환하는 쿼리를 수행하는 ajax 호출을 사용하고 있다고 생각합니다.

어떤 기술을 사용하고 있습니까?

---

닮은 단어를 찾고 있다면 soundex와 일치하는 soundex 단어로 변환 할 수 있습니다.

---

몇 가지 방법을 시도했지만 잘 작동하지 않는 경우 다음과 같이 비교적 포화 된 결과를 얻을 수 있습니다. 첫째 : 모든 텍스트의 모든 단락에 대해 Google SimHash 코드를 가져 와서 데이터 베이 스에 저장합니다. 두 번째 : SimHash 코드 색인. 셋째 : 위와 같이 비교할 텍스트를 처리하고 SimHash 코드를 가져 와서 5-10과 같은 Hamming 거리를 형성하는 SimHash 인덱스로 모든 텍스트를 검색합니다. 그런 다음 유사성을 항 벡터와 비교하십시오. 이것은 빅 데이터에서 작동 할 수 있습니다.

---

1) Minhash / LSH https://en.wikipedia.org/wiki/MinHash를 사용할 수 있습니다.

(또한 참조 : http://infolab.stanford.edu/~ullman/mmds/book.pdf )

또는

2) 협업 필터링 : https://en.wikipedia.org/wiki/Collaborative_filtering

---

@ alex77의 답변에있는 링크 는 해당 기사의 저자가 독자적으로 발견 한 Sorensen-Dice Coefficient 를 가리 킵니다. 이 기사는 매우 잘 작성되었고 읽을 가치가 있습니다.

나는 결국이 계수를 내 필요에 맞게 사용하게되었습니다. 그러나 원래 계수는 다음을 처리 할 때 잘못된 결과를 생성 할 수 있습니다.

• 맞춤법 오류가 하나 포함 된 세 글자 단어 쌍 (예 : [and,amd]및
• 애너그램 인 세 글자 단어 쌍 예 : [and,dan]

첫 번째 경우에는 Dice가 0의 계수를 잘못보고하는 반면 두 번째 경우에는 계수가 오해의 소지가있는 높은 0.5로 나타납니다.

본질적으로 단어의 첫 번째와 마지막 문자를 취하고 추가 바이그램을 만드는 것으로 구성된 개선 이 제안되었습니다 .

제 생각에 개선은 3 글자 단어에만 필요합니다. 더 긴 단어는 다른 bigram이 문제를 덮는 버퍼링 효과를 가지고 있습니다. 이 개선 사항을 구현하는 코드는 다음과 같습니다.

function wordPairCount(word)
{
 var i,rslt = [],len = word.length - 1;
 for(i=0;i < len;i++) rslt.push(word.substr(i,2));
 if (2 == len) rslt.push(word[0] + word[len]);
 return rslt;
}

function pairCount(arr)
{
 var i,rslt = [];
 arr = arr.toLowerCase().split(' ');
 for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
 return rslt;
}

function commonCount(a,b)
{
 var t;
 if (b.length > a.length) t = b, b = a, a = t; 
 t = a.filter(function (e){return b.indexOf(e) > -1;});
 return t.length;
}

function myDice(a,b)
{
 var bigrams = [],
 aPairs = pairCount(a),
 bPairs = pairCount(b);
 debugger;
 var isct = commonCount(aPairs,bPairs);
 return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); 
}

$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));

*{font-family:arial;}
table
{
 width:80%;
 margin:auto;
 border:1px solid silver;
}

thead > tr > td
{
 font-weight:bold;
 text-align:center;
 background-color:aqua;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>

마지막 예에서 의도적 인 맞춤법 오류에 유의하십시오 : abraca dabra 대 abraca badra . 추가 바이그램 보정이 적용되지 않더라도보고 된 계수는 0.9입니다. 수정하면 0.91이 될 것입니다.

바라건대, 이것은이 스레드를 실행하는 다른 사람들에게 도움이 될 것입니다.

---

Given a sample text, this program lists the repository texts sorted by similarity: simple implementation of bag of words in C++. The algorithm is linear in the total length of the sample text and the repository texts. Plus the program is multi-threaded to process repository texts in parallel.

Here is the core algorithm:

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

---

The simplest and fastest way to compare similarity among abstracts is probably by utilizing the set concept. First convert abstract texts into set of words. Then check how much each set overlaps. Python's set feature comes very hand performing this task. You would be surprised to see how well this method compares to those "similar/related papers" options out there provided by GScholar, ADS, WOS or Scopus.

참고URL : https://stackoverflow.com/questions/246961/algorithm-to-find-articles-with-similar-text