4

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.

enter image description here

5
  • Buffer. For any other advise add information about your data: point, line, polygon? – Babel Jan 2 at 12:26
  • .shp point data – Karthik Yelipe Jan 2 at 12:27
  • 1
    How far away are points to be allowed to be considered as duplicates? Which QGIS version do you use? – Babel Jan 2 at 12:52
  • Can you add a screenshot showing your data? I would try DBSCAN clustering – BERA Jan 3 at 18:34
  • 5 meters, im using qgis 3.16.2 – Karthik Yelipe Jan 4 at 9:21
6

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):

  1. Use 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.

enter image description here

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.

enter image description here

  1. I show two options for deleting duplicates in case two points are close: first creating a new field identifying close points so that you can decide manually if you want to delete them and in step 3 a way to automatically make a selection that you can delete. First the creation of a new field: To get rid of the two very close points (their distance is 1.25 m), we need a maximum distance for which we consider two points to be duplicates. For demonstration purpose, I choose a value of 10 m - however, you can choose whatever distance fits your data. I now create a new attribute field using the field calculator. I create a field with type=boolean and use this expression: it returns true of the nearest point is less than 10 meters away, false if the closest points is 10 meteres or more away. Be aware: the 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
    )

enter image description here

  1. With the same approach, you can also automatically select one of two nearest points to than delete it - so you don't have to decide manually which one to delete. In the next example, the expression from above is expanded so that from two nearest point (up to a defined maximum distance) the one with the higher id is selected. For demonstration purpose, I selected this time a distance of 40 meters: thus each time two points are closer than 40 meters, one of them is selected. Use the toolbox symbol 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
    )

enter image description here

8
  • your answer may help me for solving half of my question. How can I solve this kind of situation – Karthik Yelipe Jan 4 at 9:38
  • Which half of your question? Which kind of situation do you want to solve? Without further information it's dificult to guess about what you're thinking. – Babel Jan 4 at 9:44
  • i just added an image to my question, please look in to that kind of situation – Karthik Yelipe Jan 4 at 9:55
  • And what is the problem? You can define a minimum distance and delete those points that are closer, keeping just one, see the solution. Did you try that? Where are you stuck? – Babel Jan 4 at 9:57
  • ill try that solution and get back to you – Karthik Yelipe Jan 4 at 10:01
3

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.

enter image description here

Also take a look at hamming_distance, levenshtein or longest_common_substring:

enter image description here

2
  • This is great, didn't know it! – Babel Jan 28 at 16:05
  • @babel probably best to combine with your answer, otherwise one of two "Airports" which are 100km apart get deleted – MrXsquared Jan 28 at 16:07
2

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

  • which sound similar regarding soundex
  • are within a given distance
  • but are not the first one of each group (ordered by feature id)

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"):

enter image description here


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":

enter image description here

# 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:

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.