GNU bug report logs - #77942
31.0.50; replace-region-contents gets stuck

Previous Next

Full log

Message #29 received at 77942 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 77942 <at> debbugs.gnu.org
Subject: Re: bug#77942: 31.0.50; replace-region-contents gets stuck
Date: Mon, 21 Apr 2025 15:32:17 -0700

On 4/21/25 14:11, Stefan Monnier wrote:
> Paul, IIUC you've played with this algorithm.  Would you be tempted to
> try and improve that situation where the replacement text is*much*
> smaller the text it replaces?

My quick reaction is that you'd need a different algorithm than the 
Myers-Ukkonen algorithm used by GNU diff etc. A good place to start 
might be here:

A. Andoni, R. Krauthgamer and K. Onak, "Polylogarithmic Approximation 
for Edit Distance and the Asymmetric Query Complexity," FOCS 2010, 
377-386, <https://doi.org/10.1109/FOCS.2010.43>.

... though this is just the tip of an iceberg that I haven't had time to 
look into. If there's real interest in this (it'd be some work) I can 
ask a colleague who's more of an expert....

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.