title: SQL (Big Query) Text Similarity
body: <p>what I want to do ist the following:
  I get data maybe in columns maybe just one string with a scheme like that:</p>
  
  <pre><code>&gt; 420-xyz-somefancytext-12.3.2018-etc...
  &gt; 4-20-xyz-somefancytext-12.3.2018-etc...
  &gt; 4-250-xyz-somefancyothertext-13.3.2018-etc...
  &gt; 4-230-xyz-somefancyothertext-14.3.2018-etc...
  </code></pre>
  
  <p>The use case wants to detect the the first two rows. Because the first number is very similar and the text and of course the date. What comes to my mind is something like the edit or cosine distance to measure this similarity. </p>
  
  <p>I also implemented a very easy UDF in BigQuery:</p>
  
  <pre><code> CREATE TEMPORARY FUNCTION similariry(Name1 STRING, Name2 STRING)
    RETURNS FLOAT64
    LANGUAGE js AS """
      var _extend = function(dst) {
        var sources = Array.prototype.slice.call(arguments, 1);
        for (var i=0; i&lt;sources.length; ++i) {
          var src = sources[i];
          for (var p in src) {
            if (src.hasOwnProperty(p)) dst[p] = src[p];
          }
        }
        return dst;
      };
  
      var Levenshtein = {
        /**
         * Calculate levenshtein distance of the two strings.
         *
         * @param str1 String the first string.
         * @param str2 String the second string.
         * @return Integer the levenshtein distance (0 and above).
         */
        get: function(str1, str2) {
          // base cases
          if (str1 === str2) return 0;
          if (str1.length === 0) return str2.length;
          if (str2.length === 0) return str1.length;
  
          // two rows
          var prevRow  = new Array(str2.length + 1),
              curCol, nextCol, i, j, tmp;
  
          // initialise previous row
          for (i=0; i&lt;prevRow.length; ++i) {
            prevRow[i] = i;
          }
  
          // calculate current row distance from previous row
          for (i=0; i&lt;str1.length; ++i) {
            nextCol = i + 1;
  
            for (j=0; j&lt;str2.length; ++j) {
              curCol = nextCol;
  
              // substution
              nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
              // insertion
              tmp = curCol + 1;
              if (nextCol &gt; tmp) {
                nextCol = tmp;
              }
              // deletion
              tmp = prevRow[j + 1] + 1;
              if (nextCol &gt; tmp) {
                nextCol = tmp;
              }
  
              // copy current col value into previous (in preparation for next iteration)
              prevRow[j] = curCol;
            }
  
            // copy last col value into previous (in preparation for next iteration)
            prevRow[j] = nextCol;
          }
  
          return nextCol;
        }
  
      };
  
      var the_Name1;
  
      try {
        the_Name1 = decodeURI(Name1).toLowerCase();
      } catch (ex) {
        the_Name1 = Name1.toLowerCase();
      }
  
      try {
        the_Name2 = decodeURI(Name2).toLowerCase();
      } catch (ex) {
        the_Name2 = Name2.toLowerCase();
      }
  
      return 1 - Levenshtein.get(the_Name1, the_Name2) / the_Name1.length;
  
    """;
  
    WITH strings AS (
    SELECT NULL          string1, NULL        string2 UNION ALL
      SELECT 'test'       string1, NULL        string2 UNION ALL
      SELECT NULL          string1, 'test'        string2 UNION ALL
      SELECT 'CRATE'      string1, 'TRACE'        string2 UNION ALL
      SELECT 'MARTHA'     string1, 'MARHTA'     string2 UNION ALL
      SELECT 'DWAYNE'     string1, 'DUANE'        string2 UNION ALL
      SELECT 'DIXON'      string1, 'DICKSONX'   string2 UNION ALL
      SELECT 'Dunningham' string1, 'Cunningham' string2 UNION ALL
      SELECT 'Abroms'     string1, 'Abrams'     string2 UNION ALL
      SELECT 'Lampley'    string1, 'Campley'    string2 UNION ALL
      SELECT 'Jonathon'   string1, 'Jonathan'   string2 UNION ALL
      SELECT 'Jeraldine'  string1, 'Gerladine'  string2 UNION ALL
      SELECT 'test'       string1, 'blank'        string2 UNION ALL
      SELECT 'everybody'  string1, 'every'        string2 UNION ALL
      SELECT 'a'          string1, 'aaa'        string2 UNION ALL
      SELECT 'Géraldine'  string1, 'Gerladine'  string2 UNION ALL
      SELECT 'Jérôme'     string1, 'Jerome'     string2 UNION ALL
      SELECT 'ça'          string1, 'ca'        string2 UNION ALL
      SELECT 'Üwe'          string1, 'Uwe'        string2 
    )
    SELECT string1, string2, similariry(string1, string2) my_sim
    FROM   strings
    ORDER  BY my_sim DESC
  </code></pre>
  
  <p>It measures the similarity of the two columns. But what I need is a algorithm which measures the similarity of the rows. So this means I have to check every row with every other row. I not sure how to do it and how do it the most efficient way. In the end a table of the rows with a high similarity should be generated. </p>