Compare each element in an array to each other

Question

I need to compare a 1-dimensional array, in that I need to compare each element of the array with each other element. The array contains a list of strings sorted from longest to the shortest. No 2 items in the array are equal however there will be items with the same length. Currently I am making N*(N+1)/2 comparisons (127.8 Billion) and I'm trying to reduce the number of over all comparisons.

I have implemented a feature that basically says: If the strings are different in length by more than x percent then don't bother they not equal, AND the other guys below him aren't equal either so just break the loop and move on to the next element.

I am currently trying to further reduce this by saying that: If element A matches element C and D then it stands to reason that elements C and D would also match so don't bother checking them (i.e. skip that operation). This is as far as I've factored since I don't currently know of a data structure that will allow me to do that.

The question here is: Does anyone know of such a data structure? or Does anyone know how I can further reduce my comparisons?

My current implementation is estimated to take 3.5 days to complete in a time window of 10 hours (i.e. it's too long) and my only options left are either to reduce the execution time, which may or may not be possible, or distrubute the workload accross dozens of systems, which may not be practical.

Update: My bad. Replace the word equal with closely matches with. I'm calculating the Levenstein distance

The idea is to find out if there are other strings in the array which closely matches with each element in the array. The output is a database mapping of the strings that were closely related.

Here is the partial code from the method. Prior to executing this code block there is code that loads items into the datbase.

    public static void RelatedAddressCompute() {
        TableWipe("RelatedAddress");

        decimal _requiredDistance = Properties.Settings.Default.LevenshteinDistance;

        SqlConnection _connection = new SqlConnection(Properties.Settings.Default.AML_STORE);
        _connection.Open();

        string _cacheFilter = "LevenshteinCache NOT IN ('','SAMEASABOVE','SAME')";

        SqlCommand _dataCommand = new SqlCommand(@"
        SELECT
            COUNT(DISTINCT LevenshteinCache)
        FROM
            Address
        WHERE 
            " + _cacheFilter + @"
        AND
            LEN(LevenshteinCache) > 12", _connection);
        _dataCommand.CommandTimeout = 0;
        int _addressCount = (int)_dataCommand.ExecuteScalar();

        _dataCommand = new SqlCommand(@"
        SELECT 
            Data.LevenshteinCache,
            Data.CacheCount
        FROM            
            (SELECT
                DISTINCT LevenshteinCache,
                COUNT(LevenshteinCache) AS CacheCount
            FROM
                Address
            WHERE 
                " + _cacheFilter + @"
            GROUP BY 
                LevenshteinCache) Data
        WHERE 
            LEN(LevenshteinCache) > 12
        ORDER BY 
            LEN(LevenshteinCache) DESC", _connection);
        _dataCommand.CommandTimeout = 0;
        SqlDataReader _addressReader = _dataCommand.ExecuteReader();

        string[] _addresses = new string[_addressCount + 1];
        int[] _addressInstance = new int[_addressCount + 1];
        int _itemIndex = 1;
        while (_addressReader.Read()) {
            string _address = (string)_addressReader[0];
            int _count = (int)_addressReader[1];
            _addresses[_itemIndex] = _address;
            _addressInstance[_itemIndex] = _count;
            _itemIndex++;
        }

        _addressReader.Close();
        decimal _comparasionsMade = 0;
        decimal _comparisionsAttempted = 0;
        decimal _comparisionsExpected = (decimal)_addressCount * ((decimal)_addressCount + 1) / 2;
        decimal _percentCompleted = 0;
        DateTime _startTime = DateTime.Now;
        Parallel.For(1, _addressCount, delegate(int i) {
            for (int _index = i + 1; _index <= _addressCount; _index++) {
                _comparisionsAttempted++;
                decimal _percent = _addresses[i].Length < _addresses[_index].Length ? (decimal)_addresses[i].Length / (decimal)_addresses[_index].Length : (decimal)_addresses[_index].Length / (decimal)_addresses[i].Length;
                if (_percent < _requiredDistance) {
                    decimal _difference = new Levenshtein().threasholdiLD(_addresses[i], _addresses[_index], 50);
                    _comparasionsMade++;
                    if (_difference <= _requiredDistance) {
                        InsertRelatedAddress(ref _connection, _addresses[i], _addresses[_index], _difference);
                    }
                }
                else {
                    _comparisionsAttempted += _addressCount - _index;
                    break;
                }
            }
            if (_addressInstance[i] > 1 && _addressInstance[i] < 31) {
                InsertRelatedAddress(ref _connection, _addresses[i], _addresses[i], 0);
            }
            _percentCompleted = (_comparisionsAttempted / _comparisionsExpected) * 100M;
            TimeSpan _estimatedDuration = new TimeSpan((long)((((decimal)(DateTime.Now - _startTime).Ticks) / _percentCompleted) * 100));
            TimeSpan _timeRemaining = _estimatedDuration - (DateTime.Now - _startTime);
            string _timeRemains = _timeRemaining.ToString();
        });
    }

InsertRelatedAddress is a function that updates the database, and there are 500,000 items in the array.

Answer 1

OK. With the updated question, I think it makes more sense. You want to find pairs of strings with a Levenshtein Distance less than a preset distance. I think the key is that you don't compare every set of strings and rely on the properties of Levenshtein distance to search for strings within your preset limit. The answer involves computing the tree of possible changes. That is, compute possible changes to a given string with distance < n and see if any of those strings are in your set. I supposed this is only faster if n is small.

It looks like the question posted here: Finding closest neighbour using optimized Levenshtein Algorithm.

Answer 2

More info required. What is your desired outcome? Are you trying to get a count of all unique strings? You state that you want to see if 2 strings are equal and that if 'they are different in length by x percent then don't bother they not equal'. Why are you checking with a constraint on length by x percent? If you're checking for them to be equal they must be the same length. I suspect you are trying to something slightly different to determining an exact match in which case I need more info. Thanks Neil