배열의 각 요소를 서로 다른 요소와 비교해야하므로 1 차원 배열을 비교해야합니다. 배열에는 가장 긴 문자열부터 가장 짧은 문자열까지 정렬 된 문자열 목록이 들어 있습니다. 배열에있는 2 개의 항목은 동일하지만 동일한 길이의 항목이 있습니다. 현재 N * (N + 1)/2 비교 (1278 억)를 만들고 있으며 모든 비교의 수를 줄이려고합니다.배열의 각 요소를 서로 비교하십시오.
기본적으로 다음과 같은 기능을 구현했습니다. 문자열의 길이가 x % 이상 차이가 나지 않는 경우 해당 문자열이 동일하지 않으며 그 아래에있는 다른 사람들이 동일하지 않으므로 루프를 중단하십시오. 다음 요소로 이동하십시오.
현재 요소 A가 요소 C와 D와 일치하면 요소 C와 D도 일치하므로 요소 검사가 필요하지 않습니다 (즉, 해당 작업 건너 뛰기) . 이것은 내가 현재 그렇게 할 수있는 데이터 구조를 알지 못하기 때문에 필자가 고려한 것입니다.
여기에 질문이 있습니다. 누구나 그러한 데이터 구조를 알고 있습니까? 또는 누구든지 내가 비교를 줄일 수있는 방법을 알고 있습니까?
내 현재 구현은 10 시간의 시간 창 (예 : 너무 길다)에서 완료하는 데 3.5 일이 걸릴 것으로 예상되며 남은 유일한 옵션은 실행 시간을 줄이거 나 가능하지 않을 수도 있고 수십 개의 시스템에서 작업 부하를 분산 시키십시오. 이는 실용적이지 않을 수 있습니다.
업데이트 : 불량. 동등한 단어를를 (를)와 (으)로 바꿉니다. Levenstein 거리를 계산하고 있습니다.
아이디어는 배열에 배열의 각 요소와 거의 일치하는 다른 문자열이 있는지 확인하는 것입니다. 출력은 밀접하게 관련된 문자열의 데이터베이스 매핑입니다.
다음은이 메소드의 부분 코드입니다. 이 코드 블록을 실행하기 전에 항목을 데이터베이스에로드하는 코드가 있습니다.
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는 데이터베이스를 업데이트하는 함수로, 배열에 500,000 개의 항목이 있습니다.
길이가 다른 문자열 쌍은 정의에 따라 서로 같지 않아야합니다.길이가 X % 차이가 나는 이유는 무엇입니까? 또한 현재 알고리즘의 의사 코드 또는 코드를 게시하는 것이 좋습니다. – DGH
다음 내용을 명확히하십시오. 산출물은 무엇입니까? – Ramon