<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Devesh Kashyap on Medium]]></title>
        <description><![CDATA[Stories by Devesh Kashyap on Medium]]></description>
        <link>https://medium.com/@kashyapdevesh20?source=rss-16b8f0176e6b------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*4VIycgHuzyQdl2Hblm38cQ.jpeg</url>
            <title>Stories by Devesh Kashyap on Medium</title>
            <link>https://medium.com/@kashyapdevesh20?source=rss-16b8f0176e6b------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 16:08:44 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kashyapdevesh20/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Why Algorithms Grow Up: From Big O to Big AI]]></title>
            <link>https://medium.com/@kashyapdevesh20/why-algorithms-grow-up-from-big-o-to-big-ai-962cecbe3299?source=rss-16b8f0176e6b------2</link>
            <guid isPermaLink="false">https://medium.com/p/962cecbe3299</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[llm]]></category>
            <dc:creator><![CDATA[Devesh Kashyap]]></dc:creator>
            <pubDate>Sat, 02 Aug 2025 21:11:40 GMT</pubDate>
            <atom:updated>2025-08-02T21:14:42.349Z</atom:updated>
            <content:encoded><![CDATA[<h4>Tracing the path from classic string matching to modern LLMs</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/0*47uAW1SIdaVvU0YB.jpg" /></figure><p>The evolutions of algorithm isn’t always dictated by reduction in time complexities or space optimization. Even though they’re the major driving forces behind algorithmic optimizations especially under resource-constrained environment. In many cases, however, advancements focus less on speed and more on <strong>adaptability</strong>, expanding an algorithm’s scope to handle complex inputs, nuanced behaviors, or changing user demands and configurations even at the cost of increased complexity.</p><p>In this article, I’ll explore this idea with the textbook-favorite <strong>Longest Common Subsequence</strong> (LCS) problem and examining how it evolved to address broader use cases through <strong>Levenshtein distance</strong>, <strong>Damerau-Levenshtein</strong>, and the lesser-known yet efficient <strong>Zhao variant</strong>.</p><p>Finally, we’ll see how these classic string matching algorithms still power key components of today’s <strong>GenAI</strong> and <strong>LLM</strong> systems from <strong>fuzzy retrieval</strong> and <strong>token alignment</strong> to <strong>output evaluation</strong>. Far from obsolete, they form a crucial bridge between deterministic logic and probabilistic language models.</p><h3>Longest Common Subsequence (LCS)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/1*u63T-E-fZ4V0qUX4D30SFA.jpeg" /></figure><p>Starting with the earliest algorithm, LCS was introduced in 1950s by <strong>Richard Bellman</strong>. The core idea is to find the longest common subsequence i.e., the sequence of common characters that may or may not be contiguous in the original strings.</p><p>Once the LCS is identified, one could theoretically transform one string into another by discarding the non-matching characters and inserting the missing ones at the appropriate positions.</p><p><strong>Code:</strong></p><pre>def calculate_lcs(s1, s2, dp, i, j):<br>    if i &lt;0 or j &lt; 0:<br>        return 0<br><br>    if dp[i][j] != -1:<br>        return dp[i][j]<br><br>    if s1[i] == s2[j]:<br>        dp[i][j] = 1 + calculate_lcs(s1, s2, dp, i - 1, j - 1)<br>    else:<br>        dp[i][j] = max(<br>            calculate_lcs(s1, s2, dp, i - 1, j),<br>            calculate_lcs(s1, s2, dp, i, j - 1)<br>        )<br><br>    return dp[i][j]<br><br><br>def longest_common_subsequence(s1, s2):<br>    dp = [[-1] * (len(s2)) for _ in range(len(s1))]<br>    return calculate_lcs(s1, s2, dp, len(s1), len(s2))</pre><p>This naturally raises a few important questions:</p><ol><li>What additional operations should be considered for an actual transformation?</li><li>What metric should we use to measure how similar or different two strings are?</li></ol><p>To address this, we introduce <strong>edit operations </strong>specifically, <strong>insertion</strong> and <strong>deletion </strong>each with a cost of 1.<br> If a character needs to be changed, we can model this as a <strong>deletion followed by an insertion</strong>, incurring a total cost of 2.</p><p>So, using LCS, a simple way to compute the edit-like distance was formulated:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/0*STPvPToKWcQtty0f" /></figure><p>The next logical step was to ask:</p><blockquote>Can we optimize further by introducing a <strong>replacement</strong> operation (with cost 1), which can replace the delete-insert pair (cost 2) with a single operation?</blockquote><p>This leads us into <strong>Levenshtein Distance</strong>, which builds upon the foundation of LCS by introducing replacement as a valid operation, thereby capturing string similarity more effectively.</p><h3><strong>Levenshtein Distance</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/259/0*3Cn3tmpJcchsfItL" /></figure><p>The <strong>Levenshtein distance</strong> was developed in 1965 by <strong>Vladimir Levenshtein</strong>. It has a new <strong>replacement operation</strong> alongside the traditional <strong>insertion</strong> and <strong>deletion</strong> operations. This enhances the model of edit distance by allowing characters to be directly substituted rather than deleted and then inserted.</p><p>The code is updated as follows:</p><pre>def calculate_ld_score(s1, s2, dp, i, j):<br>    if i &lt; 0:<br>        return j + 1<br>    if j &lt; 0:<br>        return i + 1<br><br>    if dp[i][j] != -1:<br>        return dp[i][j]<br><br>    if s1[i] == s2[j]:<br>        dp[i][j] = calculate_ld_score(s1, s2, dp, i - 1, j - 1)<br>    else:<br>        dp[i][j] = 1 + min(<br>            calculate_ld_score(s1, s2, dp, i, j - 1),     # Insert<br>            calculate_ld_score(s1, s2, dp, i - 1, j),     # Remove<br>            calculate_ld_score(s1, s2, dp, i - 1, j - 1)  # Replace<br>        )<br>    return dp[i][j]<br><br>def levenshtein_distance(s1, s2):<br>    dp = [[-1] * len(s2) for _ in range(len(s1))]<br>    return calculate_ld_score(s1, s2, dp, len(s1) - 1, len(s2) - 1)</pre><p>In this case, it’s also important to understand the bottom up dynamic programming method as it will help understand later optimizations.</p><pre>def levenshtein_distance(s1, s2):<br>    m, n = len(s1), len(s2)<br>    dp = [[0] * (n + 1) for _ in range(m + 1)]<br><br>    # Base cases:<br>    for i in range(m + 1):<br>        dp[i][0] = i  <br><br>    for j in range(n + 1):<br>        dp[0][j] = j  <br><br>    # Fill DP table<br>    for i in range(1, m + 1):<br>        for j in range(1, n + 1):<br>            if s1[i - 1] == s2[j - 1]:<br>                dp[i][j] = dp[i - 1][j - 1]  # No operation needed<br>            else:<br>                dp[i][j] = min(<br>                    dp[i - 1][j] + 1,      # Deletion<br>                    dp[i][j - 1] + 1,      # Insertion<br>                    dp[i - 1][j - 1] + 1   # Substitution<br>                )<br><br>    return dp[m][n]</pre><p>Here, we can observe that while the Big O time complexity remains the <strong>same O(m × n)</strong> , the actual computation time may slightly increase in practice. This is because the algorithm now evaluates an additional path at each decision point due to the inclusion of the replacement operation.</p><p>Nevertheless, the code structure remains syntactically similar, with the addition of a new case for character replacement seamlessly integrated into the logic.</p><p>But this raises an interesting edge case:</p><p>Suppose we compare the strings <strong>“ab”</strong> and <strong>“ba”</strong>. Using only <strong>insert</strong>, <strong>delete</strong>, and <strong>replace</strong>, the minimum number of operations is:</p><ol><li>Replace &#39;a&#39; with &#39;b&#39;</li><li>Replace &#39;b&#39; with &#39;a&#39;</li></ol><p>Total cost: <strong>2</strong></p><p>However, <strong>intuitively</strong>, these two strings are only <strong>one adjacent swap away</strong> from being equal. A <strong>single transposition</strong> (swap) of the last two characters would suffice.</p><h3><strong>Damerau-Levenshtein</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*DLiN5wHyATnLT1ctmQ4t5Q.jpeg" /></figure><p>To handle above edge cases more efficiently, the <strong>Damerau-Levenshtein distance</strong> introduces a fourth operation:<br> <strong>Transposition: </strong>the adjacent swapping of characters.</p><p>This allows the algorithm to capture common human typing errors (like mistyping “<strong>hte</strong>” instead of “<strong>the</strong>”) more effectively.</p><p>The modified top down dynamic programming code is as follows:</p><pre>def calculate_dld_score(s1, s2, dp, i, j):<br>    if i &lt; 0:<br>        return j + 1<br>    if j &lt; 0:<br>        return i + 1<br><br>    if dp[i][j] != -1:<br>        return dp[i][j]<br><br>    if s1[i] == s2[j]:<br>        dp[i][j] = calculate_dld_score(s1, s2, dp, i - 1, j - 1)<br>    else:<br>        insert_op = calculate_dld_score(s1, s2, dp, i, j - 1)      # Insert<br>        delete_op = calculate_dld_score(s1, s2, dp, i - 1, j)      # Delete<br>        replace_op = calculate_dld_score(s1, s2, dp, i - 1, j - 1) # Replace<br><br>        dp[i][j] = 1 + min(insert_op, delete_op, replace_op)<br><br>        # Check for transposition condition<br>        if i &gt; 0 and j &gt; 0 and s1[i] == s2[j - 1] and s1[i - 1] == s2[j]:<br>            transpose_op = calculate_dld_score(s1, s2, dp, i - 2, j - 2)<br>            dp[i][j] = min(dp[i][j], 1 + transpose_op)<br><br>    return dp[i][j]<br><br>def damerau_levenshtein_distance(s1, s2):<br>    dp = [[-1] * len(s2) for _ in range(len(s1))]<br>    return calculate_dld_score(s1, s2, dp, len(s1) - 1, len(s2) - 1)</pre><p>The bottom up dynamic table code is updated as follows:</p><pre>def damerau_levenshtein_distance(s1, s2):<br>    m, n = len(s1), len(s2)<br><br>    # dp[i][j] = DLD between s1[0..i-1] and s2[0..j-1]<br>    dp = [[0] * (n + 1) for _ in range(m + 1)]<br><br>    # Base cases<br>    for i in range(m + 1):<br>        dp[i][0] = i<br>    for j in range(n + 1):<br>        dp[0][j] = j<br><br>    # Fill DP table<br>    for i in range(1, m + 1):<br>        for j in range(1, n + 1):<br>            cost = 0 if s1[i - 1] == s2[j - 1] else 1<br><br>            dp[i][j] = min(<br>                dp[i - 1][j] + 1,        # Deletion<br>                dp[i][j - 1] + 1,        # Insertion<br>                dp[i - 1][j - 1] + cost  # Substitution<br>            )<br><br>            # Transposition check<br>            if i &gt; 1 and j &gt; 1 and s1[i - 1] == s2[j - 2] and s1[i - 2] == s2[j - 1]:<br>                dp[i][j] = min(<br>                    dp[i][j],<br>                    dp[i - 2][j - 2] + 1  # Transposition<br>                )<br><br>    return dp[m][n]</pre><p>Even though the <strong>Big O time complexity remains O(m × n)</strong>, the practical computation time again increases due to the additional check for transpositions at each step. Nonetheless, it enables a more accurate and realistic measure of string similarity in many real-world applications.</p><p>Curious readers might notice a key limitation in the standard Damerau-Levenshtein algorithm:</p><ol><li><strong>Transpositions are limited to adjacent characters</strong> (e.g., swapping “ab” ↔ “ba”). However, in many real-world cases such as OCR errors, typing mistakes, or noisy data, <strong>non-adjacent but matching characters may need to be swapped</strong> to reduce the edit distance further.</li><li>Why are we storing entire memoization table when we really care about previous two rows in case of bottom up dynamic programming approach.</li></ol><p>These limitations were then covered in the Zhao variation of Damerau-Levenshtein.</p><h3>Zhao-Damerau-Levenshtein</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*dkiJExDwW7o0OtCdUC3w8Q.jpeg" /></figure><p>The Zhao variation of Damerau-Levenshtein allowed more flexible, non-adjacent transpositions while maintaining efficiency using clever indexing and memory of character positions.</p><p>For the purpose of current article, I’m using the production ready snippet currently being used in the <strong>RapidFuzz </strong>library <strong>( </strong><a href="https://github.com/rapidfuzz/RapidFuzz/blob/main/src/rapidfuzz/distance/DamerauLevenshtein_py.py"><strong>link </strong></a><strong>)</strong></p><pre><br>def _damerau_levenshtein_distance_zhao(s1, s2):<br>    maxVal = max(len(s1), len(s2)) + 1<br>    last_row_id = {}<br>    last_row_id_get = last_row_id.get<br>    size = len(s2) + 2<br>    FR = [maxVal] * size<br>    R1 = [maxVal] * size<br>    R = list(range(size))<br>    R[-1] = maxVal<br><br>    for i in range(1, len(s1) + 1):<br>        R, R1 = R1, R<br>        last_col_id = -1<br>        last_i2l1 = R[0]<br>        R[0] = i<br>        T = maxVal<br><br>        for j in range(1, len(s2) + 1):<br>            diag = R1[j - 1] + (s1[i - 1] != s2[j - 1])<br>            left = R[j - 1] + 1<br>            up = R1[j] + 1<br>            temp = min(diag, left, up)<br><br>            if s1[i - 1] == s2[j - 1]:<br>                last_col_id = j  # last occurrence of s1_i<br>                FR[j] = R1[j - 2]  # save H_k-1,j-2<br>                T = last_i2l1  # save H_i-2,l-1<br>            else:<br>                k = last_row_id_get(s2[j - 1], -1)<br>                l = last_col_id  # noqa:  E741<br><br>                if (j - l) == 1:<br>                    transpose = FR[j] + (i - k)<br>                    temp = min(temp, transpose)<br>                elif (i - k) == 1:<br>                    transpose = T + (j - l)<br>                    temp = min(temp, transpose)<br><br>            last_i2l1 = R[j]<br>            R[j] = temp<br><br>        last_row_id[s1[i - 1]] = i<br><br>    return R[len(s2)]</pre><p>There are few noteworthy points here:</p><ol><li>The production code uses the <strong>rolling rows optimization</strong> in the memoization table. Instead of storing the entire DP matrix, it only retains the current and previous rows since only these are needed to compute the new cell values.</li><li>By maintaining last_row_id and last_col_id, the algorithm keeps track of the last occurrences of each character in s1 and s2. However, by enforcing the conditions (j - l) == 1 and (i - k) == 1, transpositions are restricted to adjacent (or nearly adjacent) characters. Even though older indices are stored, this ensures that transpositions remain limited to pairwise swaps, rather than full substring movements.</li><li>The rest of the comparison logic remains consistent: at each decision point, the algorithm calculates the cost of insertion, deletion, and substitution based on the DP values. It then checks for a valid transposition using the conditions mentioned above. Finally, it selects the operation with the lowest cost and uses it to populate the memoization table for subsequent computations.</li></ol><p>Now that we’ve explored how classical algorithms evolved to handle fuzziness and human error, it opens up a new realm of questions:</p><p>In the age of <strong>semantic search</strong>, <strong>vector databases</strong>, and <strong>LLM-powered retrieval</strong>, where meaning often matters more than spelling</p><blockquote>Are algorithms like Damerau-Levenshtein still relevant?</blockquote><blockquote>Or have they become relics of a pre-embedding era, quietly replaced by cosine similarities and attention weights?</blockquote><p>The answer might surprise you.</p><p>Far from being obsolete, classic string-edit algorithms like <strong>Levenshtein </strong>and <strong>Damerau-Levenshtein</strong> are quietly powering some of the most practical, high-impact layers in today’s Generative AI stacks.</p><h3>The Jenga Tower of GenAI Systems</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/248/1*_fYOPHqUahB4ah5KmcYahw.jpeg" /></figure><p>Most modern GenAI applications resemble a <strong>Jenga tower, </strong>an unstable mix of black-box components (LLMs) and deterministic glue (retrieval, filters, evaluation, ranking).</p><p>When things wobble, developers typically reach for two tools:</p><ol><li><strong>LLM Output Control Parameters</strong></li></ol><p>temperature: Adjusts randomness</p><p>top_k / top_p: Constrain or expand sampling diversity</p><p>max_tokens: Cap response length</p><p>frequency_penalty / presence_penalty: Reduce repetitive output</p><p>2. <strong>Prompt Engineering</strong></p><p>Iteratively refining instructions or input phrasing to coerce better answers</p><p>But there’s a third, underused stabilizer…</p><h3>The Overlooked Layer: Edit Distance Algorithms</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/0*Zis7AxdBznhE5ASZ.gif" /></figure><p>Edit distance and string similarity techniques can quietly but dramatically enhance GenAI system performance across four major fronts:</p><h4>1. <strong>Input Query Preprocessing</strong></h4><p>Before the prompt even reaches the LLM, cleaning it using string-edit algorithms can improve outcomes:</p><ul><li>Fix typos, normalize names, standardize terms</li><li>Use fuzzy matching to correct misspelled entities</li><li>Improve entity linking and slot filling in structured prompts</li></ul><h4>2. <strong>Retrieval Augmentation (RAG) Optimization</strong></h4><p>In RAG systems, retrieval quality is everything. String-based algorithms help by:</p><ul><li>Re-ranking documents retrieved via vector similarity</li><li>Identifying near-duplicate content</li><li>Filtering out irrelevant or misaligned documents</li><li>Detecting paraphrases or alternate phrasings at the lexical level</li></ul><h4>3. LLM <strong>Evaluation Metrics</strong></h4><p>LLM evaluation metrics heavily use these distance algorithms for token overlap and string similarity calculation. The major evaluation metrics are:</p><p><strong>BLEU (</strong>Bilingual Evaluation Understudy):</p><ul><li>Compares n-grams in the generated output with reference text.</li><li>Relies on <strong>exact string matches</strong> for unigrams, bigrams, etc.</li><li>Penalizes shorter outputs with a brevity penalty.</li><li>Heavy reliance on <strong>token similarity</strong>, <strong>word order</strong>, and <strong>precision</strong>.</li></ul><p><strong>ROUGE </strong>(Recall-Oriented Understudy for Gisting Evaluation)</p><p>A suite of metrics including:</p><ul><li><strong>ROUGE-N</strong>: n-gram overlap (like BLEU but recall-oriented)</li><li><strong>ROUGE-L</strong>: based on <strong>Longest Common Subsequence (LCS)</strong></li><li><strong>ROUGE-W</strong>: weighted LCS for more nuanced scoring.</li></ul><p>Particularly popular in <strong>summarization evaluation</strong>.</p><p><strong>METEOR </strong>(Metric for Evaluation of Translation with Explicit ORdering)</p><p>Improves upon BLEU by considering:</p><ul><li><strong>Exact word matches</strong></li><li><strong>Stemmed word matches</strong></li><li><strong>Synonym matches</strong></li><li>Uses <strong>Levenshtein distance</strong> to align generated text with references.</li></ul><p>Incorporates both <strong>precision and recall</strong>, and penalizes disordered matches.</p><h4>4. Vector DB Fallbacks</h4><p>Many production-grade vector databases include <strong>hybrid retrieval</strong> capabilities combining <strong>vector similarity</strong> with <strong>string distance</strong> or lexical matching. For ex:</p><ul><li><strong>Elasticsearch </strong>combines <strong>BM25</strong> lexical scoring with <strong>fuzzy queries</strong> (based on Levenshtein distance) and is ideal for hybrid retrieval where precision matters</li><li><strong>Qdrant s</strong>upports hybrid search by fusing vector scores with metadata filters with payload filters which can include exact or fuzzy string fields</li></ul><h3>Conclusion</h3><p>Through this article, I’ve aimed to show that foundational algorithms like <strong>LCS, Levenshtein, and Damerau-Levenshtein</strong> are far from obsolete. Instead of being replaced, they’ve evolved layering new operations, adapting to fuzzier inputs, and extending their relevance into modern applications.</p><p>Their journey reflects a deeper truth about algorithmic progress:</p><blockquote><strong>It’s not always about reducing time or space complexity, but about expanding adaptability, handling edge cases, and aligning closer with real-world demands.</strong></blockquote><p>From <strong>typo correction</strong> and <strong>document retrieval</strong> to <strong>token alignment</strong> and <strong>LLM evaluation</strong>, these algorithms quietly underpin some of the most advanced systems in today’s AI stack. As we continue building smarter models and systems, it’s worth remembering that innovation often grows by standing on the shoulders of these time-tested, resilient ideas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/498/0*wjmDtLkSeR1WZATA.gif" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=962cecbe3299" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Part 1 : Reverse-Engineering RapidFuzz]]></title>
            <link>https://medium.com/@kashyapdevesh20/part-1-reverse-engineering-rapidfuzz-736955d5723a?source=rss-16b8f0176e6b------2</link>
            <guid isPermaLink="false">https://medium.com/p/736955d5723a</guid>
            <category><![CDATA[development]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[github]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[open-source]]></category>
            <dc:creator><![CDATA[Devesh Kashyap]]></dc:creator>
            <pubDate>Mon, 07 Jul 2025 08:45:44 GMT</pubDate>
            <atom:updated>2025-07-07T08:45:44.242Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Part 1 : Reverse-Engineering RapidFuzz</strong></h3><h4><strong>A beginner-friendly </strong>walkthrough to understand structure, tests, and internals of Python libraries</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lutUK3sirm0XVtQZgEoemg.jpeg" /><figcaption>Source : <a href="https://newtechaudit.ru/nechetkoe-sravnenie-strok-s-pomoshhyu-rapidfuzz/">https://newtechaudit.ru/nechetkoe-sravnenie-strok-s-pomoshhyu-rapidfuzz/</a></figcaption></figure><p>Hello Readers,</p><p>I’m starting a new series on exploring the world of python OSS, providing a beginner friendly introduction while dissecting the optimized string matching library RapidFuzz.</p><h3>Why RapidFuzz ?</h3><p>RapidFuzz serves as an ideal learning ground as:</p><h4>1.✅ Real-World Utility, Minimal Bloat</h4><p>RapidFuzz is a production-ready library used in search engines, NLP pipelines, and data cleaning. Yet, it’s compact enough to explore without feeling overwhelmed, unlike massive frameworks like TensorFlow or Django.</p><h4>2. 🧠Algorithmically Rich but Still Understandable</h4><p>It implements core string similarity algorithms (like Levenshtein, Jaro-Winkler, etc.), offering an excellent balance of <strong>applied computer science</strong> and <strong>practical Python</strong> ,perfect for learners who want to understand real implementations, not just toy examples.</p><h4>3. ⚙️Python + C++ Hybrid Design</h4><p>RapidFuzz has both <strong>pure Python</strong> and <strong>C++ backends</strong>, and it smartly switches between them at runtime. This gives learners a rare chance to see:</p><ol><li>How native extensions speed up Python.</li><li>How bindings and wrappers work</li><li>How fallback logic is designed</li></ol><h4>4. 🧪Clean and Focused Test Suite</h4><p>The test suite is compact, Pytest-based, and clearly organized. This makes it easy to:</p><ol><li>Learn how to run and trace tests.</li><li>See how small, focused unit tests drive development.</li><li>Use tests as a gateway to understand functionality.</li></ol><h4>5. 📦Modern, Maintainable Project Setup</h4><p>RapidFuzz uses a modern build system (pyproject.toml, CMake integration, CI via GitHub Actions), making it an excellent reference for:</p><ol><li>Understanding how pip installs native modules.</li><li>How cross-language builds work.</li><li>How to debug install/build issues.</li></ol><h4>6. 👁️Actively Maintained and Well-Documented</h4><p>The repo is active, well-structured, and has a responsive maintainer (Max Bachmann 🙌). Plus, the README is minimal but useful, and the function names are intuitive, making it beginner-friendly without being overly simplified.</p><h4>7. 🌱Great First Step Before Bigger Projects</h4><p>It’s small enough to understand within a few sessions but complex enough to expose us to:</p><ol><li>Performance optimization</li><li>Native code integration</li><li>Real-world testing and deployment practices</li></ol><p>We can read more about RapidFuzz performance in comparison to standard FuzzyWuzzy in below resources:</p><ol><li>Read Max Bachmann’s answer on <a href="https://stackoverflow.com/questions/52631291/vectorizing-or-speeding-up-fuzzywuzzy-string-matching-on-pandas-column/61371170#61371170">Vectorizing or Speeding up Fuzzywuzzy String Matching on PANDAS Column</a> using RapidFuzz</li><li><a href="https://medium.com/@bewin4u/fuzzy-matching-for-million-row-address-dataset-with-rapidfuzz-and-splink-b704eaf1fda9">Usage &amp; Comparison of RapidFuzz on a million row dataset</a></li></ol><blockquote><strong>Side Note:</strong></blockquote><blockquote>Props to the author of second article for identifying the browser JS workaround for disconnecting google collab notebooks 😝. Even though the mentioned method no longer works, the latest workaround which “may” work is :</blockquote><pre>function keepAliveProgrammatically() {<br>  document.querySelector(&#39;colab-connect-button&#39;).shadowRoot.querySelector(&quot;#connect&quot;).click();<br>}<br><br>// Clicks compute resources button every 6 seconds<br>const keepAliveProgrammaticallyInterval = setInterval(() =&gt; {<br>    keepAliveProgrammatically();<br>}, 6000); <br><br>// clearInterval(keepAliveProgrammaticallyInterval); {To stop the code}</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*-P1e0HlmaIYcNEjj.jpg" /></figure><p>anyways, let’s not get distracted and get going🤭</p><h3><strong>🧭 </strong>Python OSS Checklist</h3><p>With evolving project structures, extensive test suites, and increasingly complex architectures built by diverse developers across organizations (each with their own coding styles and performance goals), it’s difficult to define a one-size-fits-all framework for analysing open-source repositories.</p><p>However, what I can offer is a <strong>flexible checklist</strong> , a set of key things to look for and consider when diving into any Python OSS project for the first time.</p><ol><li>📖<strong>Project Purpose</strong></li></ol><ul><li>What problem does the library solve?</li><li>Is there a clear README or documentation?</li></ul><p><strong>2. </strong>🗂️<strong>Folder Structure</strong></p><ul><li>What are the major directories (src/, tests/, docs/, etc.)?</li><li>Is it monolithic or modular?</li></ul><p><strong>3.️ </strong>⚙️<strong>Installation &amp; Setup</strong></p><ul><li>Can we install it locally using pip install -e .?</li><li>Does it use setup.py, pyproject.toml, or both?</li><li>Are there build steps (e.g., CMake, Makefile, compiled extensions)?</li></ul><p><strong>4.</strong>🧪<strong> Test Suite</strong></p><ul><li>What testing framework is used (Pytest, Unittest)?</li><li>How are tests organized — per module, per feature?</li><li>Is there a way to run all or individual tests easily?</li></ul><p><strong>5. </strong>🔍<strong>Entry Points</strong></p><ul><li>Where does the main functionality start (__init__.py, CLI, etc.)?</li><li>What are the most frequently used modules or classes?</li></ul><p><strong>6. </strong>🧠<strong>Core Logic</strong></p><ul><li>Which files contain the main algorithms or operations?</li><li>Are there multiple implementations (e.g., Python and C++)?</li></ul><p><strong>7. </strong>🚦<strong>Continuous Integration</strong></p><ul><li>Are GitHub Actions or other CI tools configured?</li><li>What kind of checks are automated?</li></ul><p><strong>8.</strong>📦<strong> Dependencies</strong></p><ul><li>What dependencies does the project use?</li><li>Are they pinned or flexible? Do they affect compatibility?</li></ul><p><strong>9. </strong>🛠️<strong>Build &amp; Packaging</strong></p><ul><li>Does it build a wheel (bdist_wheel)?</li><li>Is it available on PyPI? How is it versioned?</li></ul><p><strong>10. </strong>📊<strong>Performance Optimizations</strong></p><ul><li>Is there any use of C/C++, NumPy, or JIT compilation?</li><li>Are there mentions of benchmarks or performance metrics?’</li></ul><h3><strong>RapidFuzz — Deep Dive</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mnSnagt49HNb_NcsE0pEpA.png" /><figcaption>GitHub Link : <a href="https://github.com/rapidfuzz/RapidFuzz">https://github.com/rapidfuzz/RapidFuzz</a></figcaption></figure><h3>Initial Observation</h3><p>Navigating to the GitHub repository, there are a few noteworthy points available in the first viewing, such as:</p><ol><li>It’s a multi-language project, uses Python and C++ for the main logic and most probably Cython as the bridge</li><li>Supports latest python version and the lib is available on PyPI and conda-forge</li><li>Uses GitHub actions for documentation updation and PyPI release</li><li>The CI pipeline is green, meaning all tests are running sucessfully and has an overall 79 % test coverage</li><li>The project has MIT license which is very permissive, allowing reuse and modifications</li><li>Finally, the project has 29 developers working on it, which is not directly useful but gives us some idea around the scope and reliability of the project ( not always true)</li><li>There are .gitmodules (<strong>reference to another external Git repositories, treated as a dependency within main project</strong>.) present in the project’s root directory, which indicates that a recursive clone using git clone --recursive &lt;repo-url&gt; is required</li></ol><h3>Local Source Installation</h3><p>After forking and cloning the project, the first step is to <strong>create a virtual environment</strong>. This ensures an isolated workspace and helps avoid conflicts with other Python packages on our system.</p><p>Before diving into the codebase, it’s good practice to:</p><ul><li>✅ <strong>Install the project locally</strong></li><li>✅ <strong>Run the full test suite</strong> (if available)</li></ul><p>This helps confirm that the code is functioning as expected and sets a baseline for our exploration.</p><p>We immediately notice a pyproject.toml file in the root of the repository — a clear indicator that the project follows <strong>PEP 517/518 standards</strong> for modern Python packaging.</p><blockquote>Fun fact, TOML’s full form is <strong>Tom’s Obvious, Minimal Language</strong> and was created by <strong>Tom Preston-Werner</strong>, co-founder of GitHub. Subtle, much?😆</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/0*bgSFOdvnQWZvcg0-.gif" /></figure><p>Anyways, as a rule of thumb:</p><ol><li>If a project contains a setup.py or pyproject.toml, it can usually be installed directly via pip install . or pip install -e .. The necessary <strong>build system, dependencies, and entry points</strong> are typically defined inside these files, and pip will handle them automatically.</li><li>On the other hand, if only a requirements.txt file is provided, we’ll need to:</li></ol><ul><li>Manually install the dependencies with pip install -r requirements.txt.</li><li>Then run any custom setup or initialization steps ourself.</li><li>Handle version mismatches, redundant dependencies, or outdated packages manually if issues arise.</li></ul><p>This is one reason why projects using pyproject.toml are considered more modern and robust — they offer a more <strong>streamlined, reproducible, and standard way to build and install Python libraries</strong>.</p><p>Now we can install the library in <strong>editable mode</strong> using:</p><pre>pip install -e .</pre><p>Here’s what happens:</p><ul><li>pip reads configuration from pyproject.toml.</li><li>The -e flag means &quot;editable&quot; — any local changes we make to the source code will immediately reflect in our virtual environment.</li><li>The package is linked rather than copied, making it ideal for debugging or development.</li></ul><p>To confirm that the install was successful we can :</p><ol><li>Open <strong>Python REPL</strong> and try:</li></ol><p>import rapidfuzz print(rapidfuzz.__version__)</p><p>2. Or navigate to local environment’s Lib/site-packages or lib/pythonX.X/site-packages folder and check for a rapidfuzz entry.</p><p>It’s important to understand the structure of the installation file (in this project, pyproject.toml) to get a clear view of the dependencies, installation steps, and build configuration.</p><h3>Under the Hood: Decoding pyproject.toml</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/440/0*N76Adu0lrKGW-ldu.png" /><figcaption>Boon or Bane? More, like BOOM !</figcaption></figure><p>GitHub Link : <a href="https://github.com/rapidfuzz/RapidFuzz/blob/main/pyproject.toml">https://github.com/rapidfuzz/RapidFuzz/blob/main/pyproject.toml</a></p><p>The pyproject.toml file defines the installation and build configuration used by pip and other modern Python packaging tools. It acts as a standardized entry point for building, installing, and configuring Python projects.</p><p>In most open-source projects (including <strong>RapidFuzz</strong>), pyproject.toml is <strong>hand-crafted</strong> by the maintainer to define:</p><ul><li>Build system requirements</li><li>Package metadata</li><li>Formatting, linting, and type-checking tools</li><li>Optional dependencies</li></ul><p>However, tools like <strong>Poetry</strong>, <strong>Flit</strong>, or <strong>Hatch</strong> can also <strong>generate </strong><strong>pyproject.toml </strong>dynamically. For example:</p><ul><li>Running poetry init or hatch new will automatically scaffold a basic configuration file for our project.</li></ul><p>The TOML syntax can be referred from this <a href="https://learnxinyminutes.com/toml/">resource</a>, it’s straight forward and functionally analogues to python’s dictionary.</p><h3><strong>RapidFuzz’s TOML File</strong></h3><p>This is a brief overview of the tables and key-value pairs present in the RapidFuzz’s pyproject.tomlin the sequence they appear:</p><h4>🏗️ 1. Build System Configuration</h4><pre>[build-system]<br>requires = [&quot;scikit-build-core&quot;, &quot;Cython&quot;]<br>build-backend = &quot;scikit_build_core.build&quot;</pre><ul><li>Uses <strong>scikit-build-core</strong> to compile C++ code (via CMake under the hood).</li><li>Uses <strong>Cython</strong> to bridge Python ↔ C++.</li><li>Enables building native extensions for performance.</li></ul><h4>📦 2. Project Metadata</h4><pre>[project]<br>name = &quot;RapidFuzz&quot;<br>requires-python = &quot;&gt;= 3.9&quot;</pre><ul><li>Declares the project name, Python version support, authorship, license, and homepage/docs links.</li><li>dynamic = [&quot;version&quot;] means version is auto-extracted from source code (__init__.py).</li></ul><h4>🔌 3. Optional Dependencies &amp; Entry Points</h4><pre>[project.optional-dependencies]<br>all = [&quot;numpy&quot;]</pre><ul><li>numpy is optional — likely for faster array-level operations.</li><li>pyinstaller40 entry-point hints integration with PyInstaller.</li></ul><h4>⚙️ 4. Native Build &amp; Fallback Strategy</h4><pre>[tool.scikit-build]</pre><ul><li>Includes/excludes specific .cxx files for source distribution.</li><li>Tries to build <strong>C++ extension</strong> if possible.</li></ul><blockquote>If C++ build fails, gracefully falls back to pure Python (important for portability).</blockquote><blockquote>Shows custom success/failure messages like “C++ Extension built successfully” or “Falling back to Python extension”.</blockquote><blockquote>We can control this with environment variables too — more on that in the test/deployment module!</blockquote><h4>🧪 5. Testing Configuration</h4><pre>[tool.pytest.ini_options]<br>testpaths = [&quot;tests&quot;]</pre><ul><li>Uses <strong>Pytest</strong> as the test framework.</li><li>Custom options to show local variables, enforce strict marker/config usage, and log outputs.</li></ul><h4>🧹 6. Linting &amp; Code Quality Tools</h4><pre>[tool.black]<br>[tool.mypy]<br>[tool.pylint]<br>[tool.ruff]</pre><ul><li><strong>Black</strong> for formatting</li><li><strong>Mypy</strong> for type checking</li><li><strong>Pylint</strong> for code smells</li><li><strong>Ruff</strong> for blazing-fast linting (with extensive rules from Flake8, Pylint, Pytest, etc.)</li></ul><h4>🛠️ 7. Build Wheels with CI</h4><pre>[tool.cibuildwheel]</pre><ul><li>Enables building platform-specific wheels (e.g., Windows, Linux, macOS).</li><li>Runs tests automatically using pytest and hypothesis.</li></ul><h4>🧩 What’s Interesting?</h4><p>The messages.after-success entries in [tool.scikit-build] are conditionally <strong>overwritten</strong> based on the [[overrides]] section. These messages and conditions guide how the build system behaves:</p><ul><li>If system CMake is available and meets criteria, the C++ backend is built.</li><li>Otherwise, the installer silently falls back to the pure Python backend — maintaining compatibility across platforms.</li></ul><p><em>📌 </em>During Pip installation, while wheels hide build-time messages, RapidFuzz still performs a runtime check and falls back to Python if native extensions are missing or crash</p><h3>The Road Ahead</h3><p>Now that we understand how the installation process works — and how the system dynamically chooses between a native C++ build or a fallback Python implementation at runtime — we’re ready to move on to the next crucial step: exploring and executing the project’s test suite.</p><p>This phase is not just about confirming that the code runs — it’s where we begin to uncover how core functionalities are verified, how bugs are prevented through regression tests, and how well-structured tests can actually guide us through the internal design of the library.</p><p>In upcoming modules, we’ll go even deeper — analyzing the actual string similarity algorithms RapidFuzz uses (like Levenshtein, Jaro-Winkler, and others), understanding how they’re implemented efficiently, and how Python and C++ versions coexist under the hood.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/498/0*Z61a6dIHgTE4MDxV.gif" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=736955d5723a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Creating GUI for rendering Reinforcement Learning algorithms]]></title>
            <link>https://medium.com/@kashyapdevesh20/creating-gui-for-rendering-reinforcement-learning-algorithms-7a0e9a2aee6f?source=rss-16b8f0176e6b------2</link>
            <guid isPermaLink="false">https://medium.com/p/7a0e9a2aee6f</guid>
            <category><![CDATA[ui]]></category>
            <category><![CDATA[ux]]></category>
            <category><![CDATA[gui]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <dc:creator><![CDATA[Devesh Kashyap]]></dc:creator>
            <pubDate>Fri, 30 Jul 2021 10:27:18 GMT</pubDate>
            <atom:updated>2021-07-30T10:27:18.680Z</atom:updated>
            <content:encoded><![CDATA[<h4>Part 1</h4><h4><strong>INTRODUCTION</strong></h4><p>Last weekend, I was tinkering with OpenAI gym’s environment using the StableBaselines3 library and I thought it would be somewhat cool &amp; efficient if there was some GUI that offered simple dropdown options for all benchmark RL algorithms and environments. Maybe this GUI could be extended by adding cloud server support along with options for creating our own custom environments or testing some new algorithms. So, like any other sane person, I surfed the internet in search of such software (open-source or otherwise), but to my dismay, I couldn’t find any. So, here I’m attempting to create such software which could satisfy the above requirements while still looking on fleek.</p><p>Now, with wishful ambitions out of the way, let’s look at the problem pragmatically and chart out a plan while assessing the problems I may face.</p><p>Let’s divide the problem into small steps:</p><ol><li><strong>Learning GUI programming</strong>: I have no knowledge of GUI programming, so I’ve to learn almost everything from scratch. I’ve decided to make this a proper downloadable application rather than a web app.</li><li><strong>Writing the algorithms</strong>: I’ve decided to write all the benchmark algorithms myself so that I can better understand them and implement them seamlessly.</li><li><strong>UI/UX design</strong>: Although this is a personal project, I would like the end product to be simple &amp; elegant.</li><li><strong>Integration</strong></li><li><strong>Broadcasting</strong>: Publishing the application to some online package distributer, so that it could be easily downloaded.</li></ol><p>I have decided to give bi-weekly updates of my project through medium posts to keep me motivated and keep track of the progress.</p><h3><strong>STEP 1: LEARNING GUI PROGRAMMING</strong></h3><p>Since I’ve sound knowledge of C++ &amp; Python, I started my search by keeping these languages as a base and extending from here in order to avoid the paradox of choices.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*EyS1UyI4qfX2Uh7x" /><figcaption>Paradox of Choices</figcaption></figure><h3>Cross-Platform or Linux only?</h3><p>Now, the next big question to ask is whether I want my application to be only Linux-based or be cross-platform. Having a Linux-based system might prove advantageous during later stages of integration where I’m linking the application to OS and have considerably fewer things to worry about, but at the same time, it may limit the reach.</p><p>With a Linux-based system, I can work around hardware acceleration using CUDA, which I suspect might be relatively less hard compared to implementing the same for all platforms.</p><p>Another caveat to ponder around is the time invested in the project, with the internship season right around the corner, I already have many things on my plate right now, so implementing cross-platform software may turn out to be time-consuming.</p><p>Keeping the above points in mind I fired up Firefox &amp; let the hunt begin.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgfycat.com%2Fifr%2Frewardinginnocentfulmar&amp;display_name=Gfycat&amp;url=https%3A%2F%2Fgfycat.com%2Frewardinginnocentfulmar&amp;image=https%3A%2F%2Fthumbs.gfycat.com%2FRewardingInnocentFulmar-size_restricted.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gfycat" width="3840" height="2160" frameborder="0" scrolling="no"><a href="https://medium.com/media/3a06cb93316af20fec92304d78d4f300/href">https://medium.com/media/3a06cb93316af20fec92304d78d4f300/href</a></iframe><h3>Selecting Framework/Libraries</h3><p>At first glance, Qt seems like a reasonable choice, it has great community support, the codebase is well tested &amp; is pretty stable. Even though I want my application to be Linux-based only, Qt utilizes the system’s native framework, &amp; adapts accordingly. This way, not only can I go cross-platform without much effort but also focus more on my core work rather than on framework nuances.</p><p>But, if only life was this easy. The problem with Qt is, it won’t run on my system, as it happens, I had migrated from Ubuntu 20.04 “LTS” version to Ubuntu 21.04 in the hopes of GNOME 40 (which were successfully shattered). The 21.04 is based on Debian bullseye, which does not have qt5-default package in <a href="https://packages.debian.org/search?suite=all&amp;searchon=names&amp;keywords=qt5-default">the repository</a>.</p><p>One workaround would be to individually install the dependencies and link them in Qt creator every time I create a new project, but this process is not only tedious but may also break the project during its course of completion. And under no circumstance, I was willing to downgrade my system, so the search continued.</p><p>Apart from Qt, I also found <a href="http://wxwidgets.org/">wxWidgets</a>, <a href="https://www.juce.com/">JUCE</a>, <a href="http://cegui.org.uk/">CEGUI</a>, <a href="https://bitbucket.org/chromiumembedded/cef">CEF</a> &amp; <a href="https://kosenko.github.io/boost.ui/">Boost</a>. They all had issues ranging from complex licensing, unstable codebases to low community support for GUI applications.</p><p>After careful consideration, I have decided to build my application using “<a href="https://www.gtkmm.org/en/">gtkmm</a>”, which is a C++ Interface for GTK+ and GNOME. Even though Gtk3 is the current stable version present in all Linux environments, I will be using Gtk4 as Gtk3 is getting deprecated soon.</p><p>I will also be using <a href="https://glade.gnome.org/">Glade</a> Interface Designer due to its high compatibility with gtkmm.</p><h3>Resources</h3><p>I will be using the official documentation of gtkmm and Glade, as they are very comprehensive.</p><ul><li><a href="https://developer.gnome.org/gtkmm-tutorial/stable/index.html.en">Programming with gtkmm 4</a></li><li><a href="https://help.gnome.org/users/glade/stable/">Glade Interface Designer Manual</a></li><li><a href="https://wiki.gnome.org/Apps/Glade/Tutorials">Apps/Glade/Tutorials - GNOME Wiki!</a></li></ul><p>Apart from them, I will be using some existing applications built using gtkmm as references.</p><ul><li><a href="https://github.com/synfig/synfig">GitHub - synfig/synfig: This is the Official source code repository of the Synfig project</a></li><li><a href="https://github.com/uowuo/abaddon">GitHub - uowuo/abaddon: An alternative Discord client made with C++/gtkmm</a></li><li><a href="https://github.com/ZipCPU/vgasim">GitHub - ZipCPU/vgasim: A Video display simulator</a></li><li><a href="https://github.com/ashaduri/gsmartcontrol">GitHub - ashaduri/gsmartcontrol: GSmartControl - Hard disk drive and SSD health inspection tool</a></li><li><a href="https://github.com/Suzamax/Aircraft">GitHub - Suzamax/Aircraft: GTK Telegram Client (WIP!)</a></li><li><a href="https://github.com/gammasoft71/Examples_Gtkmm">GitHub - gammasoft71/Examples_Gtkmm: Shows how to use Gtkmm controls by programming code (c++17).</a></li></ul><h3>Target</h3><p>I am planning to finish constructing a rough GUI for my application by the end of this week and move on to writing the Reinforcement Learning algorithms.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgfycat.com%2Fifr%2Fquarrelsomeelasticatlanticsharpnosepuffer&amp;display_name=Gfycat&amp;url=https%3A%2F%2Fgfycat.com%2Fquarrelsomeelasticatlanticsharpnosepuffer-john-wick-chapter-3-parabellum-keanu-reeves&amp;image=https%3A%2F%2Fthumbs.gfycat.com%2FQuarrelsomeElasticAtlanticsharpnosepuffer-size_restricted.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gfycat" width="1080" height="1080" frameborder="0" scrolling="no"><a href="https://medium.com/media/e10fd237b47341bd44ce4392e786223e/href">https://medium.com/media/e10fd237b47341bd44ce4392e786223e/href</a></iframe><p>In the next article, I will post about the problems I may face during the learning stage or during the GUI construction.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7a0e9a2aee6f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>