使用Levenshtein距离在字典中寻找朋友的朋友

Question

以下是我正在尝试做的事情。 这两个词W1和W2是朋友如果Levenshtein distance这些词是1. 我应该找到朋友的所有朋友也。我试图用Bk-Tree做同样的事情。它适用于小字典（字典只包含每行一个字） 但对于较大的字典，它正在大量放缓并且运行超过一个小时仍然没有结果。

以下是我到目前为止的代码

---

#include <string> 
#include <vector> 
#include <queue> 
#include <fstream> 
#include <iostream> 
#include <algorithm> 

class BkTree { 
    public: 
     BkTree(); 
     ~BkTree(); 
     void insert(std::string m_item); 
     void get_friends(std::string center, std::deque<std::string>& friends); 
    private: 
     size_t EditDistance(const std::string &s, const std::string &t); 
     struct Node { 
      std::string m_item; 
      size_t m_distToParent; 
      Node *m_firstChild; 
      Node *m_nextSibling; 
      Node(std::string x, size_t dist);   
      bool visited; 
      ~Node(); 
     }; 
     Node *m_root; 
     int m_size; 
    protected: 
}; 

BkTree::BkTree() { 
    m_root = NULL; 
    m_size = 0; 
} 

BkTree::~BkTree() { 
    if(m_root) 
     delete m_root; 
} 

BkTree::Node::Node(std::string x, size_t dist) { 
    m_item   = x; 
    m_distToParent = dist; 
    m_firstChild = m_nextSibling = NULL; 
    visited  = false; 
} 

BkTree::Node::~Node() { 
    if(m_firstChild) 
     delete m_firstChild; 
    if(m_nextSibling) 
     delete m_nextSibling; 
} 

void BkTree::insert(std::string m_item) { 
    if(!m_root){ 
     m_size = 1; 
     m_root = new Node(m_item, -1); 
     return; 
    } 
    Node *t = m_root; 
    while(true) { 
     size_t d = EditDistance(t->m_item, m_item); 
     if(!d) 
      return; 
     Node *ch = t->m_firstChild; 
     while(ch) { 
      if(ch->m_distToParent == d) { 
       t = ch; 
       break; 
      } 
      ch = ch->m_nextSibling; 
     } 
     if(!ch) { 
      Node *newChild = new Node(m_item, d); 
      newChild->m_nextSibling = t->m_firstChild; 
      t->m_firstChild = newChild; 
      m_size++; 
      break; 
     } 
    } 
} 

size_t BkTree::EditDistance(const std::string &left, const std::string &right) { 
    size_t asize = left.size(); 
    size_t bsize = right.size(); 
    std::vector<size_t> prevrow(bsize+1); 
    std::vector<size_t> thisrow(bsize+1); 

    for(size_t i = 0; i <= bsize; i++) 
     prevrow[i] = i; 

    for(size_t i = 1; i <= asize; i ++) { 
     thisrow[0] = i; 
     for(size_t j = 1; j <= bsize; j++) { 
      thisrow[j] = std::min(prevrow[j-1] + size_t(left[i-1] != right[j-1]), 
        1 + std::min(prevrow[j],thisrow[j-1])); 
     } 
     std::swap(thisrow,prevrow); 
    } 
    return prevrow[bsize]; 
} 


void BkTree::get_friends(std::string center, std::deque<std::string>& flv) { 
    if(!m_root) return ; 
    std::queue< Node* > q; 
    q.push(m_root); 

    while(!q.empty()) { 
     Node *t = q.front(); 
     q.pop(); 
     if (!t) continue; 

     size_t d = EditDistance(t->m_item, center); 
     if(d == 1) { 
      if (t->visited == false) { 
       flv.push_back(t->m_item); 
       t->visited = true; 
      } 
     } 
     Node *ch = t->m_firstChild; 
     q.push(ch); 
     while(ch) { 
      if(ch->m_distToParent >= 1) 
       q.push(ch); 
      ch = ch->m_nextSibling; 
     } 
    } 
    return; 
} 

int main(int argc, char **argv) { 
    BkTree *pDictionary = new BkTree(); 

    std::ifstream dictFile("word.list"); 
    std::string line; 
    if (dictFile.is_open()) { 
     while (! dictFile.eof()) {    
      std::getline (dictFile,line); 
      if (line.size()) { 
       pDictionary->insert(line); 
      } 
     } 
     dictFile.close(); 
    } 
    std::deque<std::string> flq; 
    pDictionary->get_friends("aa", flq); 
    int counter = 0; 
    while (!flq.empty()) { 
     counter++; 
     std::string nf = flq.front(); 
     flq.pop_front(); 
     pDictionary->get_friends(nf, flq); 
    } 
    std::cout << counter << std::endl; 
    return 0; 
} 

上提高速度，或任何其他合适的数据结构中的任何意见。

假设以下是我的词典。

aa 
aah 
aal 
aam 
aami 
aamii 
aaaaaaaaaaaaaaaaaaaaaaaaa 

我试图找到aa的social network答案是5。

Answer 1

请详细阅读Fast and Easy Levenshtein distance using a Trie以了解解决此问题的有效方法。

在您的示例代码中，不是“朋友的朋友”，编辑距离为2（或0）？您可能会停止使用深度优先搜索，直接比较Levenshtein距离是0还是2（0表示编辑被第二个关系“解除”，例如A→B的编辑距离为1，B→> C的编辑距离为1，正好取消了A→B编辑，使A→C之间的编辑距离为零）。

这也似乎与word ladders puzzles有关。一个巨大的可视化的变化爆炸是可用here。我想你的算法，你想找到长度为2的单词对之间的所有路径？也许将它表达为所有对的词梯问题会给你一个新的方法？