<p>As stated in his comment, The OP is actually looking for all the pairs with edit distance of less than 2.</p>

<p>Given an input of n words, a naive approach would be to make n(n-1)/2 comparisons, but less comparison may be required when L in an edit distance which is a <a href="https://en.wikipedia.org/wiki/Edit_distance#Properties" rel="nofollow">metric space for strings</a>. </p>

<p>Levenshtein distance is a metric space, and satisfies the 4 required metric axioms - including the triangle inequality.</p>

<p><strong>Edit:</strong></p>

<p>Given this, we can use the method proposed by Sergey Brin (Google's co-founder) in his paper <a href="http://www.vldb.org/conf/1995/P574.PDF" rel="nofollow">Near Neighbor Search in Large Metric Spaces</a> back in 1995, to solve our problem.</p>

<p>Quoting from the paper: Given a metric space (X, d), a data set Y ⊆ X, a query point x ∈ X, and a range r ∈ R, the near neighbors of x are the set of points y ∈ Y, such that d(x, y) ≤ r.</p>

<p>In this paper, Brin introduced GNAT (Geometric Near-neighbor Access Tree) - a data structure to solve this problem. Brin actually test the performance of his algorithm using the Levenshtein distance (which he calls "Edit distance") against two text corpora.</p>

<p>Over the years GNAT become well-known and widely used. Some improvements to GNAT where suggested in <a href="https://arxiv.org/pdf/1605.05944v1.pdf" rel="nofollow">Geometric Near-neighbor Access Tree (GNAT) revisited</a> - Fredriksson 2016.</p>
More efficient way of finding edit distance over a large array
<p>I have a large array of words (300k words) and I want to find the edit distance between each word, so I was just iterating over it and doing running through this version of the levenstein algorithm:</p>

<pre><code>unsigned int edit_distance(const std::string&amp; s1, const std::string&amp; s2)
{
    const std::size_t len1 = s1.size(), len2 = s2.size();
    std::vector&lt;std::vector&lt;unsigned int&gt;&gt; d(len1 + 1, std::vector&lt;unsigned int&gt;(len2 + 1));
d[0][0] = 0;
for (unsigned int i = 1; i &lt;= len1; ++i) d[i][0] = i;
for (unsigned int i = 1; i &lt;= len2; ++i) d[0][i] = i;

for (unsigned int i = 1; i &lt;= len1; ++i)
    for (unsigned int j = 1; j &lt;= len2; ++j)
        // note that std::min({arg1, arg2, arg3}) works only in C++11,
        // for C++98 use std::min(std::min(arg1, arg2), arg3)
        d[i][j] = std::min({ d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1) });
return d[len1][len2];
}
</code></pre>

<p>So what I was wondering is, if there was a more efficient way of doing this, I heard about Levenshtein Autonoma but I wasn't sure if that would be any more efficient. </p>

<p>I would imagine that there you could avoid processing the same thing over and over again by preprocessing something but I have no idea how to actually achieve it (some approximate calculations would be to preprocess everything would be around 10^28 operations so that would not be an improvement)</p>