Having duplications in the data is quite natural and removing them is quite hard if we didn't have the same attributes.
In QGIS there are tools to eliminate the duplications but only if the data is the same according to the attributes. What tool can I use to identify duplicates at a specific distance? The data type is Point shapefile.
You have two options, depending on whether the points are actual duplicates (exactely the same point) or if the are "almost" duplicates (very close to one another):
Menu Processing / Toolbox / Delete duplicate geometries. This will eliminate duplicate points. On the screenshot, I created several points as actual duplicates - to make them visible, I addel labels for each point. You can see e.g. that there are four duplicate points in the center, labeled as 1, 19, 21 and 25. We want to get rid of three of them.
After you run the tool, see the next screenshot for the output: you see that the actual duplicates were deleted, just one point is retained. However, on the upper part on the left, we have quasi-duplicates: two points that are very close. As you see from the measurement tool in the first screenshot, points 16 and 26 are less than a few meters away from each other.
overlay_nearest expression only works with QGIS version 3.16 (or later, see changelog, for older versions have a look at refFunctions plugin).One you have the field (see screenshot below), you can sort the attribute table and delete on of the duplicates.
if (
array_to_string (
array_foreach (
overlay_nearest(
@layer,
$geometry
),
distance (
$geometry,
@element
)
)
) < 10,
true,
false
)
Select by expression and paste the following expression, than you just have to delete all selected points to get rid of duplicates (duplicates being defined as points closer than 40 meters): if (
if (
array_to_string (
array_foreach (
overlay_nearest(
@layer,
$geometry
),
distance (
$geometry,
@element
)
)
) < 40,
array_to_string (
overlay_nearest(
@layer,
"id"
)
),
false
) > "id",
false,
true
)
You can also use some of the fuzzy matching expression.
Here an example using soundex:
As expression I am using $id = array_first(array_agg($id,soundex("name"))), which groups names by their soundex representation and only returns the first one (ordered by their feature id) of each group. To illustrate here a gif using select by expression. However, this will not take the distance of features to each other into account, so one of two "Hospital" on the other side of the earth will be selected. For a solution taking this into account, see my Python solution.
Also take a look at hamming_distance, levenshtein or longest_common_substring:
Here are solutions in Python, the first one is a simple script using soundex and the second one a processing tool letting you choose which algorithm to use.
1. Soundex only
selecting all features of a layer
You can then decide what to do with this selection of "duplicates", e.g. delete them or reverse the selection or whatever.
field = 'name' # fieldname containing similar sounding strings
maxdist = 1000 # maximum search distance in CRS units
layer = iface.activeLayer() # layer to operate on
# no changes needed below #
layer.removeSelection() # cleanup selection before running
for feat in layer.getFeatures(): # itereate over layer
for lookup in layer.getFeatures(): # compare to every feature of same layer
if feat.id() > lookup.id(): # only compare if not already done so
if feat.geometry().distance(lookup.geometry()) < maxdist: # only select if within given maxdistance
if QgsStringUtils.soundex(feat[field]) == QgsStringUtils.soundex(lookup[field]): # compare soundex
layer.select(feat.id()) # select if they sound similar
Here an example, the grid is 1000m*1000m for reference, layer CRS is in meters, the symbol color is categorized by soundex("name"):
Processing tool
And here a more advanced solution realized as a processing tool, letting you choose between soundex, hamming distance, levenshtein distance and longest common substring as well as "exact duplicates":
# License: GNU General Public License v3.0
from PyQt5.QtCore import QCoreApplication, QVariant
from qgis.core import (QgsField, QgsFeature, QgsProcessing, QgsExpression, QgsGeometry, QgsPoint, QgsFields, QgsWkbTypes, QgsStringUtils,
QgsProcessingAlgorithm, QgsProcessingParameterField, QgsProcessingParameterVectorLayer, QgsProcessingOutputVectorLayer, QgsProcessingParameterEnum, QgsProcessingParameterString, QgsProcessingParameterNumber)
class SelectDuplicatesBySimilarity(QgsProcessingAlgorithm):
SOURCE_LYR = 'SOURCE_LYR'
SOURCE_FIELD = 'SOURCE_FIELD'
MAX_DISTANCE = 'MAX_DISTANCE'
ALGORITHM = 'ALGORITHM'
ANDORALG = 'ANDORALG'
THRESHOLD_LEVENSHTEIN = 'THRESHOLD_LEVENSHTEIN'
THRESHOLD_SUBSTRING = 'THRESHOLD_SUBSTRING'
THRESHOLD_HAMMING = 'THRESHOLD_HAMMING'
OPERATOR = 'OPERATOR'
OUTPUT = 'OUTPUT'
def initAlgorithm(self, config=None):
self.addParameter(
QgsProcessingParameterVectorLayer(
self.SOURCE_LYR, self.tr('Source Layer'))) # Take any source layer
self.addParameter(
QgsProcessingParameterField(
self.SOURCE_FIELD, self.tr('Attribute Field to search for similarity'),'Name','SOURCE_LYR')) # Choose the Trigger field of the source layer, default if exists is 'Trigger'
self.addParameter(
QgsProcessingParameterNumber(
self.MAX_DISTANCE, self.tr('Maximum Search Distance for Duplicates in Layer CRS units'),1,10000))
self.addParameter(
QgsProcessingParameterEnum(
self.ALGORITHM, self.tr('Select the Algorithms you want to use to identify similar attributes.'),
['Exact Duplicates',
'Soundex',
'Levenshtein Distance',
'Longest Common Substring',
'Hamming Distance'],
allowMultiple=True,defaultValue=[1]))
self.addParameter(
QgsProcessingParameterEnum(
self.ANDORALG, self.tr('Choose if all selected algorithms need to fulfill criteria or only at least one'),['All','Only at least one'],defaultValue=0))
self.addParameter(
QgsProcessingParameterNumber(
self.THRESHOLD_LEVENSHTEIN, self.tr('Choose a Threshold for Levenshtein < Threshold'),0,None,True,0))
self.addParameter(
QgsProcessingParameterNumber(
self.THRESHOLD_SUBSTRING, self.tr('Choose a Threshold for Longest Common Substring > (Length of Attributevalue - Threshold)'),0,None,True,0))
self.addParameter(
QgsProcessingParameterNumber(
self.THRESHOLD_HAMMING, self.tr('Choose a Threshold for Hamming Distance > (Length of Attributevalue - Threshold)'),0,None,True,0))
self.addOutput(QgsProcessingOutputVectorLayer(self.OUTPUT, self.tr('Possible Duplicates')))
def processAlgorithm(self, parameters, context, feedback):
# Get Parameters and assign to variable to work with
layer = self.parameterAsLayer(parameters, self.SOURCE_LYR, context)
field = self.parameterAsString(parameters, self.SOURCE_FIELD, context)
maxdist = self.parameterAsDouble(parameters, self.MAX_DISTANCE, context)
th_levenshtein = self.parameterAsInt(parameters, self.THRESHOLD_LEVENSHTEIN, context)
th_substring = self.parameterAsInt(parameters, self.THRESHOLD_SUBSTRING, context)
th_hamming = self.parameterAsInt(parameters, self.THRESHOLD_HAMMING, context)
alg = self.parameterAsEnums(parameters, self.ALGORITHM, context)
ao = self.parameterAsInt(parameters, self.ANDORALG, context)
op = self.parameterAsString(parameters, self.OPERATOR, context)
total = 100.0 / layer.featureCount() if layer.featureCount() else 0 # Initialize progress for progressbar
layer.removeSelection() # clear selection before every run
#totalfeatcount = layer.featureCount()
for current, feat in enumerate(layer.getFeatures()): # iterate over source
s = None # reset selection indicator
s0 = None
s1 = None
s2 = None
s3 = None
s4 = None
th_levenshtein_new = th_levenshtein
th_substring_new = th_substring
th_hamming_new = th_hamming
if feat[field] is not None and len(str(feat[field])) > 0: # only compare if field is not empty
# recalc thresholds based on current attribute values
th_levenshtein_new = th_levenshtein_new
if th_levenshtein_new < 0: # set to 0 if it would be negative
th_levenshtein_new = 0
th_substring_new = len(str(feat[field])) - th_substring
if th_substring_new < 0: # set to 0 if it would be negative
th_substring_new = 0
th_hamming_new = len(str(feat[field])) - th_hamming
if th_hamming_new < 0: # set to 0 if it would be negative
th_hamming_new = 0
for lookupnr in range(1,feat.id(),1): # only compare to previous features, because we do not want to select the first feature of each duplicate group
lookup = layer.getFeature(lookupnr) # get the lookup-feature
if lookup[field] is not None and len(str(lookup[field])) > 0: # only compare if field is not empty
if feat.geometry().centroid().distance(lookup.geometry().centroid()) <= maxdist: # only select if within given maxdistance
if 0 in alg: # Exact Duplicates
if feat[field] == lookup[field]:
s0 = 1
else: s0 = 0
if 1 in alg: # Soundex
if QgsStringUtils.soundex(str(feat[field])) == QgsStringUtils.soundex(str(lookup[field])):
s1 = 1
else: s1 = 0
if 2 in alg: # Levenshtein
if QgsStringUtils.levenshteinDistance(str(feat[field]),str(lookup[field])) < th_levenshtein_new:
s2 = 1
else: s2 = 0
if 3 in alg: # Longest Common Substring
if len(QgsStringUtils.longestCommonSubstring(str(feat[field]),str(lookup[field]))) > th_substring_new:
s3 = 1
else: s3 = 0
if 4 in alg: # Hamming Distance:
if QgsStringUtils.hammingDistance(str(feat[field]),str(lookup[field])) > th_hamming_new:
s4 = 1
else: s4 = 0
if ao == 0: # All chosen algorithms need to match
if 0 in (s0, s1, s2, s3, s4): # Dont select current feature if at least one used algorithm returned 0
s = 0
else: # Select current feature if all algorithms returned 1 or None
s = 1
elif ao == 1: # Only at least one algorithm needs to match
if 1 in (s0, s1, s2, s3, s4): # Select current feature if at least one used algorithm returned 1
s = 1
else: # Dont select current feature if no used algorithm returned 1
s = 0
if s == 1: # select the current feature if indicator is true
layer.select(feat.id())
if feedback.isCanceled(): # Cancel algorithm if button is pressed
break
feedback.setProgress(int(current * total)) # Set Progress in Progressbar
return {self.OUTPUT: parameters[self.SOURCE_LYR]} # Return result of algorithm
def tr(self, string):
return QCoreApplication.translate('Processing', string)
def createInstance(self):
return SelectDuplicatesBySimilarity()
def name(self):
return 'SelectDuplicatesBySimilarity'
def displayName(self):
return self.tr('Select possible duplicate features by similarity (attribute and distance)')
def group(self):
return self.tr('FROM GISSE')
def groupId(self):
return 'from_gisse'
def shortHelpString(self):
return self.tr(
'This Algorithm selects possible duplicate features by their similarity. The first feature (ordered by feature id) in each group is NOT beeing selected. '
'You can choose between the following algorithms, and can also combine them: \n'
'- Exact Match: Matches if the attribue values are exactly the same \n'
'- Soundex: Matches by sound, as pronounced in English if both results are equal \n '
'- Levenshtein Distance: Matches if by measuring the difference between two sequences is lower than the threshold\n '
'- Longest Common Substring: Matches if the longest string that is a substring of compared value and greater than the threshold \n'
'- Hamming Distance: Matches if between two strings of equal length the number of positions at which the corresponding symbols are greater than the threshold \n '
'You can also choose a maximum search distance in CRS units. If the layer is not a single-point layer, the centroids are taken for distance calculation.'
)
Example:
