🕸️https://github.com/toreaurstadboss/SnomedCtTools
Snomed Ct stands form Systemized Nomenclature Of MEDicine - Clinical Terms It is an international standard of terminology used in Electronic Health Records (EHR), also known as patient journals. It has also national extensions in addition to its shared 370,000 items. Norway for example has 16,000 national (local) items.
To validate Snomed Ct codes we use the Verhoeff algorithm.
The Verhoeff algorithm calculates a checksum for error detection. Snomed Ct codes use the algorithm for the checksum, which is the last digit in its code.
It was first published in 1969 by Dutch matematician Jacobus Verhoeff. It was also discovered much later by German matematician Peter Gumm in 1985, which then included a formal proof
in addition. The theory is based upon Group theory. The algorithm detects all single digit errors (one digit wrong) or format errors, one digit
inserted or left out or transpositions (interchanging two adjacent digits). The research paper is here:
An easier overview of the algorithm is exaplained on the Wikipedia article of Verhoeff algorithm: 📖 https://en.wikipedia.org/wiki/Verhoeff_algorithm First off we consider a multiplication table for the algorithm, D. It is also called the Cayley table, more description on that in the following Wikipedia page:
📗 https://en.wikipedia.org/wiki/Cayley_table. The Cayley table of the Dihedral group D5 is used in the Verhoeff algorithm.
VerhoeffValidator.cs - Multiplication matrix - Cayley table D of Dihedral (5 sided polygon) Group D5 (P
private static readonly int[,] D =
{
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 0, 6, 7, 8, 9, 5 },
{ 2, 3, 4, 0, 1, 7, 8, 9, 5, 6 },
{ 3, 4, 0, 1, 2, 8, 9, 5, 6, 7 },
{ 4, 0, 1, 2, 3, 9, 5, 6, 7, 8 },
{ 5, 9, 8, 7, 6, 0, 4, 3, 2, 1 },
{ 6, 5, 9, 8, 7, 1, 0, 4, 3, 2 },
{ 7, 6, 5, 9, 8, 2, 1, 0, 4, 3 },
{ 8, 7, 6, 5, 9, 3, 2, 1, 0, 4 },
{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }
};
The permutations table P is applying permutations for the numbers 0-9 iteratively with the permutation (1 5 8 9 4 2 7 0)(3 6) We end up with an iterative mapping of permutations for each row
1 -> 5 -> 8 -> 9 ^ | | v 0 <- 7 <- 2 <- 4 3 <-> 6
VerhoeffValidator.cs - Permutations matrix P
private static readonly int[,] P =
{
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 5, 7, 6, 2, 8, 3, 0, 9, 4 },
{ 5, 8, 0, 3, 7, 9, 6, 1, 4, 2 },
{ 8, 9, 1, 6, 0, 4, 3, 5, 2, 7 },
{ 9, 4, 5, 3, 1, 2, 6, 8, 7, 0 },
{ 4, 2, 8, 6, 5, 7, 3, 9, 0, 1 },
{ 2, 7, 9, 3, 8, 0, 6, 4, 1, 5 },
{ 7, 0, 4, 6, 9, 1, 3, 2, 5, 8 }
};
The Verhoeff validation check then becomes the following method, where we perform an algorithm that does the following calculation for the checksum c :
VERHOEFF ALGORITHM - CHECKSUM CALCULATION 1. Create an array n from the digits of the number, read right to left (rightmost digits become n_0 and so on) - i.e. reversal of the digits 2. Initialize the checksum c to zero : c = 0. 3. For each index i of the array n, starting at zero, replace c with the following : D(c, P(i mod 8, n_i))
Note that the calculations here uses array lookup of D and P. The mod here is the standard modulo operator, % , n_i is the n-th element. 4. Check that the final value of c is 0 : c = 0
/// <summary>
/// Checks whether a number has a valid Verhoeff check digit.
/// </summary>
/// <param name="number">The numeric identifier, including its check digit.</param>
/// <returns><see langword="true" /> when the number passes the Verhoeff check.</returns>
public static bool IsValidVerhoeff(string code)
{
int[] digits = code
.Select(character => int.Parse(character.ToString()))
.Reverse()
.ToArray();
int checksum = 0;
for (int index = 0; index < digits.Length; index++)
{
checksum = D[checksum, P[index % 8, digits[index]]];
}
return checksum == 0;
}
A more mathematical formulation :
VERHOEFF CHECKSUM VALIDATION
Let n = (n₀, n₁, ..., nₖ₋₁) denote the digits of the identifier in reverse order,
where n₀ is the rightmost digit.
Initialize
c₀ = 0
For each position i = 0, ..., k − 1 compute
cᵢ₊₁ = D(cᵢ, P(i mod 8, nᵢ))
where
D : {0,...,9} × {0,...,9} → {0,...,9}
is the Cayley table derived from the dihedral group D₅, and
P : {0,...,7} × {0,...,9} → {0,...,9}
is the position-dependent digit permutation.
The identifier is valid if and only if
cₖ = 0.
Snomed Ct validator
Snomed Ct codes validates in addition that the code is numerical (only digits) and has a length between 6 to 18 digits. Our validator will accept whitespace and normalizes the code be removing whitespace.
using System.Text.RegularExpressions;
namespace SnomedCtTools.Lib.Validation;
public static class SnomedCtValidator
{
/// <summary>
/// Checks if a Snomed Ct Code is valid.
/// It should be :
/// - 6 to 18 digits
/// - All numerics (this method washes away whitespace anyways)
/// - Passes the Verhoeff's dihedral check, which is checked by this
/// method internally.
/// </summary>
/// <param name="code"></param>
/// <returns></returns>
public static bool IsValidSnomedCt(string code)
{
if (string.IsNullOrWhiteSpace(code))
{
return false;
}
//normalize whitespace to allow flexibility concerning whitespace
string normalizedCode = Regex.Replace(code, @"\s+", "");
if (!normalizedCode.All(c => char.IsDigit(c)))
{
return false;
}
if (normalizedCode.Length < 6 || normalizedCode.Length > 18)
{
return false;
}
bool isValid = VerhoeffValidator.IsValidVerhoeff(normalizedCode);
return isValid;
}
}
Some unit tests validates well known Snomed Ct codes and also checks that erroneous codes are flagged as not valid code. This is done by looking at the last digit, which is the checksum and using the Verhoeff algorithm and checking we are between 6-18 digits in length as noted. And also, we normalize and remove whitespace to offer some flexibility.
using FluentAssertions;
using NUnit.Framework;
using SnomedCtTools.Lib.Validation;
namespace SnomedCtTools.Tests.Validation
{
[TestFixture]
public class SnomedCtValidatorTests
{
[Test]
[TestCase("44054006", true, Description = "diabetes type 2")]
[TestCase("440540006", false, Description = "not a snomed ct code")]
[TestCase("67148009", true, Description = "Podagra")]
[TestCase("671480091", false, Description = "not a snomed ct code")]
public void SnomedCtValidationCheckForWellknownDiseases(string code, bool expected)
{
SnomedCtValidator.IsValidSnomedCt(code).Should().Be(expected);
}
[Test]
[TestCase("24700007", true)]
[TestCase("2470", false)]
[TestCase("2470000000000000000000000000007", false)]
public void SnomedCtValidationChecksLengthCorrect(string code, bool expected)
{
SnomedCtValidator.IsValidSnomedCt(code).Should().Be(expected);
}
[Test]
[TestCase("24700007", true)]
[TestCase(" 24700007", true)]
[TestCase("24700007 ", true)]
[TestCase("2470 0007 ", true)]
[TestCase("2 470 00 07 ", true)]
public void SnomedCtValidationAcceptsWhiteSpace(string code, bool expected)
{
SnomedCtValidator.IsValidSnomedCt(code).Should().Be(expected);
}
[Test]
[TestCase("24700007", true)]
[TestCase("k24700007", false)]
[TestCase("24700007#", false)]
[TestCase("2470@k0007kk", false)]
[TestCase("2kk3k#@!470###00kk07ll", false)]
public void SnomedCtValidationCheckIlleagalChars(string code, bool expected)
{
SnomedCtValidator.IsValidSnomedCt(code).Should().Be(expected);
}
}
}
The tests passes ! (yeah, those last four also passes)
No comments:
Post a Comment